创建树与图

int[] h,e,ne;
int idx=0;
void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
}

深度搜索

public static void dfs(int start,boolean[] vis){
        vis[start]=true;
        System.out.println(start);
        time[start]=id++;//时间戳
        for(int i=h[start];i!=-1;i=ne[i]){
            int next=e[i];
            if(vis[next]){
                continue;
            }
            dfs(next,vis);
        }
    }

树的dfs序列

每一个节点都输出两遍，在对当前节点开始递归和结束递归时分别记录当前节点

 //输出树的dfs序列
    public static void dfs(int start,boolean[] vis,int[] res){
        //当前节点进入递归与出递归之前记录当前节点
        res[id++]=start;
        vis[start]=true;
        for(int i=h[start];i!=-1;i=ne[i]){
            int next=e[i];
            if(vis[next]){
                continue;
            }
            dfs(next,vis,res);
        }
        res[id++]=start;
    }

数的最大深度

在递归下一个节点之前 计算下一个节点的深度

    public static void getDeep(int start,boolean[] vis,int[] deep){
        vis[start]=true;
        for(int i=h[start];i!=-1;i=ne[i]){
            int next=e[i];
            if(vis[next]){
                continue;
            }
            deep[next]=deep[start]+1;
            getDeep(next,vis,deep);
        }
    }

通过自底向上维护每一个节点的子树节点数

每一个节点在递归子树之后维护当前节点数

    //通过自底向上维护信息
    public static void dfs(int start,boolean[] vis,int[] size){
        vis[start]=true;size[start]=1;
        for(int i=h[start];i!=-1;i=ne[i]){
            int next=e[i];
            if(vis[next]){
                continue;
            }
            dfs(next,vis,size);
            size[start]+=size[next];
        }
    }

应用：计算树节点的分数

节点分数，每一个节点对应的子树的节点数

class Solution {
    int[] head;int[] e;int[] ne;int idx=0;
    int n;
    public int countHighestScoreNodes(int[] parents) {
        n=parents.length;
        head=new int[n+10];e=new int[2*n+10];ne=new int[2*n+10];
        Arrays.fill(head,-1);
        int root=-1;
        for(int i=0;i<parents.length;i++){
            if(parents[i]==-1){
                root=i;
                continue;
            }
            add(parents[i],i);
        }

        long[] size=new long[n];
        boolean[] vis=new boolean[n];
        dfs(root,vis,size);

//         for(int i=0;i<n;i++){
//             System.out.println(size[i]+"==");
//         }

        // System.out.println("节点数"+n);


        Map<Long,Integer> score=new HashMap<Long,Integer>();

        //对于每一个节点计算分数
        for(int i=0;i<n;i++){
            long re=getScore(i,size);
            // System.out.println("节点为"+i+"==="+re);
            score.put(re,score.getOrDefault(re,0)+1);
        }

        int res=0;long maxScore=Integer.MIN_VALUE;
        Set<Map.Entry<Long,Integer>> entries=score.entrySet();
        for(Map.Entry<Long,Integer> entry:entries){
            long key=entry.getKey();
            int value=entry.getValue();
            // System.out.println("key"+key+"==="+"value"+value);
            if(key>maxScore){
                maxScore=key;
                res=value;
            }
        }

        return res;

    }

    public long getScore(int start,long[] size){
        long score=1;
        long sum=0;
        for(int i=head[start];i!=-1;i=ne[i]){
            int j=e[i];
            score*=size[j];
            sum+=size[j];
        }
        return (n-1-sum)==0? score:score*(n-1-sum);
    }

    public void dfs(int start,boolean[] vis,long[] size){
        vis[start]=true;size[start]=1;
        for(int i=head[start];i!=-1;i=ne[i]){
            int j=e[i];
            if(vis[j]){continue;}
            dfs(j,vis,size);
            size[start]+=size[j];
        }
    }


    public void add(int a,int b){
        e[idx]=b;
        ne[idx]=head[a];
        head[a]=idx++;
    }
} 

计算树的重心

    static int weightPoint=0;
    static int ans=Integer.MAX_VALUE;
    //计算树的重心
    public static void getWeight(int n,int start,boolean[] vis,int[] size){
        vis[start]=true;
        int maxPoint=0;
        size[start]=1;
        for(int i=h[start];i!=-1;i=ne[i]){
            int next=e[i];
            if(vis[next]){
                continue;
            }
            getWeight(n,next,vis,size);
            size[start]+=size[next];
            maxPoint=Math.max(maxPoint,size[next]);
        }
        //递归所有的子树之后size[start]表示start子树的所有的节点数
        maxPoint=Math.max(maxPoint,n-size[start]);
        if(maxPoint<ans){
            ans=maxPoint;
            weightPoint=start;
        }
    }

图的连通块

           //联通块数量
        static int cnt=1;


        int[] res=new int[n+1];
        Arrays.fill(res,-1);
        for(int i=1;i<=n;i++){
            if(res[i]==-1){
                cnt++;
                dfs(i,vis,res);
            }
        }
        System.out.println("联通块数量"+--cnt);

    //对每一个节点进行dfs，获得所有的联通块数量
    public static void dfs(int start,boolean[] vis,int[] res){
        res[start]=cnt;
        for(int i=h[start];i!=-1;i=ne[i]){
            int next=e[i];
            if(res[next]!=-1){
                continue;
            }
            dfs(next,vis,res);
        }
    }

广度优先遍历

广度优先队列性质：单调性和两段性
单调性：只有先访问完所有的i层节点，才能够访问i+1层节点
两段性：任意时刻，队列中只会包含 两层节点

  public static void bfs(int start,boolean[] vis,int[] deep){
        Queue<Integer> queue=new LinkedList<>();
        queue.offer(start);
        deep[start]=1;
        while (!queue.isEmpty()) {
            Integer node = queue.poll();
            vis[node]=true;
            for(int i=h[node];i!=-1;i=ne[i]){
                int next=e[i];
                if(vis[next]){
                    continue;
                }
                deep[next]=deep[node]+1;
                queue.offer(next);
            }
        }
    }

通过广度优先的方式求topsort

（1）将所有的入度为0的节点加入队列
(2)每从队列中取出一个节点，将相邻的节点入度减1 ，将更新入度之后的节点加入队列

class Solution {
    int[] e;int[] ne;int[] head;int idx=0;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        e=new int[numCourses*numCourses];ne=new int[numCourses*numCourses];head=new int[numCourses];//可能存在双向边
        Arrays.fill(head,-1);
        int n=prerequisites.length;
        int[] deg=new int[numCourses];
        for(int i=0;i<n;i++){
            int a=prerequisites[i][0];int b=prerequisites[i][1];
            add(b,a);
            deg[a]++;
        }

        Queue<Integer> queue=new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(deg[i]==0){
                queue.offer(i);
            }
        }
        int[] res=new int[numCourses];
        int index=0;
        while(!queue.isEmpty()){
            int node=queue.poll();
            res[index++]=node;
            for(int i=head[node];i!=-1;i=ne[i]){
                int j=e[i];
                deg[j]=deg[j]-1;
                if(deg[j]==0){
                    queue.offer(j);
                }
            }
        }
        if(index==numCourses){
            return res;
        }else{
            return new int[]{};
        }
    }

    public void add(int a,int b){
        e[idx]=b;
        ne[idx]=head[a];
        head[a]=idx++;
    }
}