题目

题目来源：力扣（LeetCode）

你这个学期必须选修 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 。这是不可能的。

思路分析

拓补排序

给定一个包含 n 个节点的有向图 G，我们给出它的节点编号的一种排列，如果满足：

对于图 G 中的任意一条有向边 (u,v)，u 在排列中都出现在 v 的前面。

那么称该排列是图 G 的「拓扑排序」。根据上述的定义，我们可以得出两个结论：

  • 如果图 G 中存在环（即图 G 不是「有向无环图」），那么图 G 不存在拓扑排序。这是因为假设图中存在环 x1, x2, …, xn, x1，那么 x1 在排列中必须出现在 xn 的前面，但 xn 同时也必须出现在 x1 的前面，因此不存在一个满足要求的排列，也就不存在拓扑排序；
  • 如果图 G 是有向无环图，那么它的拓扑排序可能不止一种。举一个最极端的例子，如果图 G 值包含 n 个节点却没有任何边，那么任意一种编号的排列都可以作为拓扑排序。

有了上述的简单分析，我们就可以将本题建模成一个求拓扑排序的问题了：

  • 我们将每一门课看成一个节点；
  • 如果想要学习课程 A 之前必须完成课程 B，那么我们从 B 到 A 连接一条有向边。这样以来，在拓扑排序中，B 一定出现在 A 的前面。

用有向图描述依赖关系

  • 示例：n = 6，先决条件表：[[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]]
  • 课 0, 1, 2 没有先修课，可以直接选。其余的课，都有两门先修课。
  • 我们用有向图来展现这种依赖关系（做事情的先后关系）：

image.png

  • 这种叫 有向无环图，把一个 有向无环图 转成 线性的排序 就叫 拓扑排序。
  • 有向图有 入度 和 出度 的概念：
    • 如果存在一条有向边 A —> B，则这条边给 A 增加了 1 个出度，给 B 增加了 1 个入度。
  • 所以，顶点 0、1、2 的入度为 0。顶点 3、4、5 的入度为 2。

每次只能选你能上的课

  • 每次只能选入度为 0 的课，因为它不依赖别的课，是当下你能上的课。
  • 假设选了 0，课 3 的先修课少了一门，入度由 2 变 1。
  • 接着选 1，导致课 3 的入度变 0，课 4 的入度由 2 变 1。
  • 接着选 2，导致课 4 的入度变 0。
  • 现在，课 3 和课 4 的入度为 0。继续选入度为 0 的课……直到选不到入度为 0 的课。

算法流程：

  1. 在开始排序前，扫描对应的存储空间（使用邻接表），将入度为 0 的结点放入队列。
  2. 只要队列非空，就从队首取出入度为 0 的结点，将这个结点输出到结果集中，并且将这个结点的所有邻接结点（它指向的结点）的入度减 1，在减 1 以后，如果这个被减 1 的结点的入度为 0，就继续入队。
  3. 当队列为空的时候，检查结果集中的顶点个数是否和课程数相等即可。

思考这里为什么要使用队列？（马上就会给出答案。）

在代码具体实现的时候，除了保存入度为 0 的队列，我们还需要两个辅助的数据结构：

  1. 邻接表：通过结点的索引，我们能够得到这个结点的后继结点；
  2. 入度数组：通过结点的索引，我们能够得到指向这个结点的结点个数。

这个两个数据结构在遍历题目给出的邻边以后就可以很方便地得到。

  1. /**
  2.  * @param {number} numCourses
  3.  * @param {number[][]} prerequisites
  4.  * @return {boolean}
  5.  */
  6. var canFinish = function (numCourses, prerequisites) {
  7.   const inDegree = new Array(numCourses).fill(0);// 入度数组
  8.   const map = {};// 邻接表
  9.   for (let i = 0; i < prerequisites.length; i++) {
  10.     inDegree[prerequisites[i][0]]++;// 求每一堂课的初始入度值
  11.     if (map[prerequisites[i][1]]) {// 当前课已经存在邻街表
  12.       map[prerequisites[i][1]].push(prerequisites[i][0])// 添加依赖它的后续课
  13.     } else {// 当前课不存在邻街表
  14.       map[prerequisites[i][1]] = [prerequisites[i][0]]
  15.     }
  16.   }
  17.   const queue = [];// 处理入度为0节点存到队列
  18.   for (let i = 0; i < inDegree.length; i++) {// 队列的初始化
  19.     if (inDegree[i] == 0) queue.push(i);
  20.   }
  21.   let count = 0;// 当前选的课程
  22.   while (queue.length) {
  23.     const selected = queue.shift();
  24.     count++;
  25.     const toEnQueue = map[selected];// 当前课程的后续课程
  26.     if (toEnQueue && toEnQueue.length) {
  27.       for (let i = 0; i < toEnQueue.length; i++) {
  28.         inDegree[toEnQueue[i]]--;
  29.         if (inDegree[toEnQueue[i]] == 0) {
  30.           queue.push(toEnQueue[i])
  31.         }
  32.       }
  33.     }
  34.   }
  35.   return count == numCourses;// 选修了所有的课程
  36. }