图论|207. 课程表 210. 课程表 II

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
题目链接：207. 课程表
使用拓扑排序的解法

class Solution {
    //拓扑排序解法 将有向无环图转换成线性序列
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            //准备工作
            //1.节点的入度（每次只能选入度为0的课）
            //2.依赖这门课的后续课（选当前课哪些节点的入度会被影响）’
            //如何判断选择完所有的课
            //BFS结束时，所有节点入度为0 或者 记录入列的节点个数等于门数则可以上完所有课程
            //入度数组 
            int[] inDegree=new int[numCourses];
            Arrays.fill(inDegree, 0);
            Map<Integer, List<Integer>> adjacencyList = new HashMap<>(); // 邻接表  
  
        // 初始化入度数组和邻接表  
            for (int[] prerequisite : prerequisites) {  
                inDegree[prerequisite[0]]++; // 计算课程的入度  
                if (adjacencyList.containsKey(prerequisite[1])) {  
                // 如果课程已经在邻接表中，添加依赖它的后续课程  
                    adjacencyList.get(prerequisite[1]).add(prerequisite[0]);  
                } else {  
                    // 如果课程不在邻接表中，新建一个列表存储后续课程  
                    List<Integer> list = new ArrayList<>();  
                    list.add(prerequisite[0]);  
                    adjacencyList.put(prerequisite[1], list);  
                }  
            }  
            Queue<Integer> queue=new LinkedList<>();  ;
            //度为0则入列
            for(int i=0;i<inDegree.length;i++){
                if(inDegree[i]==0){
                    queue.offer(i);
                }
            }
            int count=0;
            while (!queue.isEmpty()) {  
                int currentCourse = queue.poll(); // 出列一个课程  
                count++; // 已选课程数加1  
                if (adjacencyList.containsKey(currentCourse)) {  
                // 获取当前课程的所有后续课程  
                    for (int nextCourse : adjacencyList.get(currentCourse)) {  
                        inDegree[nextCourse]--; // 后续课程的入度减1  
                        if (inDegree[nextCourse] == 0) {  
                            // 如果入度减为0，加入队列  
                            queue.offer(nextCourse);  
                        }  
                    }  
                }  
            }  
            return count == numCourses;

        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

多了一个路径的记录

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] reslut=new int[numCourses];
        ArrayList<Integer> tmpresult=new ArrayList<Integer>();
        //存储课程的入度，即指向该节点的节点
        Queue<Integer> queue=new LinkedList<>();
        int[] inDegree=new int[numCourses];
        Arrays.fill(inDegree, 0);
        //存储课程的后续节点(HashMap>)
        HashMap<Integer,List<Integer>> map=new HashMap<>();
        for(int[] prerequisite : prerequisites){
            inDegree[prerequisite[0]]++;
            if(!map.containsKey(prerequisite[1])){
                List<Integer> list=new ArrayList<>();
                list.add(prerequisite[0]);
                map.put(prerequisite[1],list);
            }else{
                map.get(prerequisite[1]).add(prerequisite[0]);
            }
        }
        //找到入度为0的节点为先选课程
        for(int i=0;i<inDegree.length;i++){
            if(inDegree[i]==0){
                queue.offer(i);
            }
        }
        System.out.println(queue.size());
        if(queue.size()==0){
            return new int[0];
        }
        while(!queue.isEmpty()){
            Integer node=queue.poll();
            tmpresult.add(node);
            if (map.containsKey(node)) {
                List<Integer> tmpmap=map.get(node);
                for(int i=0;i<tmpmap.size();i++){
                    inDegree[tmpmap.get(i)]--;
                    if(inDegree[tmpmap.get(i)]==0){
                        queue.offer(tmpmap.get(i));
                    }
                }
            }
        }
        if(tmpresult.size()!=numCourses){
            //new int[0]是空的数组
            return new int[0];
        }else{
            for (int i = 0; i < tmpresult.size(); i++) {
                reslut[i] = tmpresult.get(i);
            }
            return reslut;
        }
            
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55