207.课程表

发表于： 分类于：
字数： 1192 阅读：≈ 3分钟

🧑‍💻 207.课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

思路

基本思想

这是一道典型的拓扑排序的题目,给定的所有课程的选择,有先修课程的概念,必须先选择先修课程,才能选择接下来的课程,这种结构可以看成是一种图,最开始的先修课程可以看成入度为零的节点,先修课程修完之后,从这个图中拿掉之后,又会出现新的入度为零的节点,也就是下一步可以修的课程

topo

在图中来看,程序设计和高等数学就是是最开始的先修课程,入度为零,修完他们之后,将其从图中拿掉,又会出现新的入度为零的课程,也就是普通物理,离散数学,算法语言,就这样修完一门拿掉一门,不断地出现入度为零的节点,就这样一直拿,一直修改

最终可以形成一个图的拓扑排序,长度是图中所有节点的数量,本题中不要求将全部的拓扑排序求出来,只需要修够规定的课程数即可

拓扑排序的思想就是,整理得到课程图的信息,一个出发点对应很多到达点,所以对于一个出发点而言,需要一个容器存储所有的到达点,故需要容器的嵌套

从给定的所有课程的信息中获得所有边的信息,之后获得所有入度点的信息,下一步就是正常的拓扑排序,先找出所有的入度为零的节点加入队列中,之后讲这些节点标记为已修完,从而这些节点的到达点的入度会减一,当出现新的入度为零的节点时,将其加入队列中

重复上述操作,当队列中没有节点时,说明拓扑排序完成,若此时拓扑排序形成的结果长度刚好是图中节点的长度,说明拓扑排序完成,可以完成选修

重点就是入度为零的节点才能选修,选修之后,对应的到达点入度减一,从而判断是否有新的入度为零的节点出现

执行流程

  1. 初始化容器,包括所有的节点及其对应的到达点的容器,以及所有节点的入度情况
  2. 将初始状态下所有入度为零的节点加入队列中,从而将他们的到达节点的入度减一
  3. 判断是不是有新的入度为零的节点出现,将新节点加入队列中
  4. 判断拓扑排序中是不是包含了所有的节点

代码

根据以上分析,得出以下代码:

 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

class Solution {
    //如何从所有的情况中找出一个合法的情况
    //拓扑排序的题目
    //广度优先遍历更好理解,就是正常的拓扑排序,之后判断是否成功排序
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //存储所有的边和节点的入度
        List<ArrayList<Integer>> edges=new ArrayList<ArrayList<Integer>>();
        int[] inNum=new int[numCourses];
        for(int i=0;i<numCourses;++i){
            edges.add(new ArrayList<Integer>());
        }
        //计算所有的边和入度
        for (int[] prerequisite : prerequisites) {
            edges.get(prerequisite[1]).add(prerequisite[0]);
            inNum[prerequisite[0]]++;
        }

        //找到所有入度为零的节点
        LinkedList<Integer> queue=new LinkedList<>();
        for(int i=0;i<inNum.length;++i){
            if(inNum[i]==0){
                queue.addLast(i);
            }
        }
		//开始拓扑排序
        int count=0;
        while(!queue.isEmpty()){
            ++count;
            int node=queue.removeFirst();
            //根据这个点拿到所有的邻接点,减小他们的入度
            List<Integer> temp=edges.get(node);
            for(int i=0;i<temp.size();++i){
                inNum[temp.get(i)]--;
                if(inNum[temp.get(i)]==0){
                    queue.addLast(temp.get(i));
                }
            }

        }
        return count==numCourses;
    }
}

总结

核心就是拓扑排序,这里使用广度优先遍历的拓扑排序更好理解,遍历一个就删除一个,同时将其到达点的入度减一