Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

课程表

Posted on In , ,
Symbols count in article: 1.9k Reading time ≈ 2 mins.

来源Leetcode第207题课程表

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

示例 1:

1
2
3
输入: 2, [[1,0]] 
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例 2:

1
2
3
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

说明:

  1. 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
  2. 你可以假定输入的先决条件中没有重复的边。

提示:

  1. 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
  2. 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
  3. 拓扑排序也可以通过 BFS 完成。

BFS拓扑排序

来源题解

  • 本题可约化为：课程安排图是否是 有向无环图(DAG)。即课程间规定了前置条件，但不能构成任何环路，否则课程前置条件将不成立。

  • 思路是通过拓扑排序判断此课程安排图是否是有向无环图(DAG)。

    • 拓扑排序是对 DAG 的顶点进行排序，使得对每一条有向边 (u, v)(u,v)，均有 uu（在排序记录中）比 vv 先出现。亦可理解为对某点 vv 而言，只有当 vv 的所有源点均出现了，vv 才能出现。

  • 通过课程前置条件列表 prerequisites 可以得到课程安排图的 邻接矩阵 adjacency，以下两种方法都会用到邻接矩阵。

拓扑排序实际上应用的是贪心算法。贪心算法简而言之：每一步最优，全局就最优。

具体到拓扑排序，每一次都从图中删除没有前驱的顶点，这里并不需要真正的做删除操作，我们可以设置一个入度数组，每一轮都输出入度为 0 的结点，并移除它、修改它指向的结点的入度（-1−1即可），依次得到的结点序列就是拓扑排序的结点序列。如果图中还有结点没有被移除，则说明“不能完成所有课程的学习”。

拓扑排序保证了每个活动（在这题中是“课程”）的所有前驱活动都排在该活动的前面，并且可以完成所有活动。拓扑排序的结果不唯一。拓扑排序还可以用于检测一个有向图是否有环。相关的概念还有 AOV 网，这里就不展开了。

算法流程：

1、在开始排序前，扫描对应的存储空间（使用邻接表），将入度为 0 的结点放入队列。

2、只要队列非空，就从队首取出入度为 0 的结点，将这个结点输出到结果集中，并且将这个结点的所有邻接结点（它指向的结点）的入度减 1，在减1 以后，如果这个被减 1 的结点的入度为 0 ，就继续入队。

3、当队列为空的时候，检查结果集中的顶点个数是否和课程数相等即可。

0210.gif

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
public boolean canFinish(int numCourses, int[][] prerequisites) {
    if(numCourses <= 0)
        return false;
    if(prerequisites.length == 0)
        return true;
    int []indegree = new int[numCourses];
    Integer ve;
    for(int [] tmp : prerequisites)
        indegree[tmp[0]]++;  //记录各节点的入度数
    LinkedList<Integer> queue = new LinkedList<>();
    for(int i = 0 ; i < numCourses ; i++)
        if(indegree[i] == 0)
            queue.addLast(i);  //入度为0的点入队尾
    while(!queue.isEmpty()){
        ve = queue.removeFirst();  //队首元素出队
        numCourses--;  //对应的课程数减一
        for(int[] tmp:prerequisites){  //在表里去掉与之有关的边
            if(tmp[1] != ve) //如果该边的起点不是出队节点，continue
                continue;
            if(--indegree[tmp[0]] == 0)  //是就删去该边，并且入度数-1
                queue.addLast(tmp[0]); //入度为0入队列
        }
    }
    return numCourses == 0;
}