一 算法流程

1. 计算每一个节点入度

   一般是用数组计算即可

2. 使用邻接表数据结构，构建图

   java里面可以申明一个数组,数组元素类型为一个list,每一个数组是一个list的引用,存储该节点所有的邻接节点

   //邻接表,外层是一个数组，每一个数组引用一个list对象，存储该节点所有的邻接节点
   List<Integer>[]graph = new ArrayList[numCourses];
   

3. 进行拓扑排序，采用BFS算法

   • 构建队列，将所有入度为0的节点进队

   • 循环（队列非空）

     • 将上一轮入队的节点出队，并且将他们的邻接节点都入队

4. 统计出入队的节点总数,如果小于图节点总数,拓扑排序失败,图中有环.否则成功

二 课程表(1,2)

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 1 使用数组存储每一个节点的入度
        // 2 构建图，使用邻接表的方法
        // 3 拓扑排序（广搜）
        //  3.1 将入度为0的节点进队
          //循环  3.2 如果队列不空
          //   3.3 第一个节点出队，将它的邻居入队
        // 4 统计出入队的节点数目，如果等于图节点数目，则拓扑排序成功，否则失败

        //1 存储度数表
        int[]degrees = new int[numCourses];
        //2 邻接表,外层是一个数组，每一个数组引用一个list对象，存储该节点所有的邻接节点
        List<Integer>[]graph = new ArrayList[numCourses];
        for(int i = 0;i<numCourses;i++){
            graph[i] = new ArrayList<>();
        }
        // 构建表与图
        for(int []item:prerequisites){
            int inNode = item[1];
            int outNode = item[0];
            degrees[outNode]++;
            graph[inNode].add(outNode);
        }
        Queue<Integer>queue = new LinkedList<>();
        //3 入度为0的进队
        for(int i =0;i<numCourses;i++){
            if(degrees[i]==0){
                queue.add(i);
            }
        }
        //计数
        int cnt = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int j =0 ;j<size;j++){
                cnt++;
                int node = queue.poll();
                for(int next:graph[node]){
                    //找到所有邻居节点
                    //入度更新
                    degrees[next]--;
                    if(degrees[next]==0){
                        //不会存在重复问题：
                        //有向图，只会将入度为0的进入队列，只会进入一次
                        queue.offer(next);
                    }
                }

            }
        }
        return cnt==numCourses;

    }
}