题目

题目来源：力扣（LeetCode）

现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例 1:

输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2:

输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

思路分析

拓补排序

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

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

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

  • 如果图 G 中存在环（即图 G 不是「有向无环图」），那么图 G 不存在拓扑排序。这是因为假设图中存在环 x1, x2, …, xn, x1，那么 x1 在排列中必须出现在 xn 的前面，但 xn 同时也必须出现在 x1 的前面，因此不存在一个满足要求的排列，也就不存在拓扑排序；

  • 如果图 G 是有向无环图，那么它的拓扑排序可能不止一种。举一个最极端的例子，如果图 G 值包含 n 个节点却没有任何边，那么任意一种编号的排列都可以作为拓扑排序。

  • 「拓扑排序」是专门应用于有向图的算法；

  • BFS 的写法就叫「拓扑排序」，这里还用到了贪心算法的思想，贪的点是：当前让入度为 0 的那些结点入队；
  • 「拓扑排序」的结果不唯一；
  • 删除结点的操作，通过「入度数组」体现，这个技巧要掌握；
  • 「拓扑排序」的一个附加效果是：能够顺带检测有向图中是否存在环，这个知识点非常重要，如果在面试的过程中遇到这个问题，要把这一点说出来。
  • 具有类似附加功能的算法还有：Bellman-Ford 算法附加的作用是可以用于检测是否有负权环

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

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

算法流程：

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

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

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

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

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

  1. /**
  2.  * @param {number} numCourses
  3.  * @param {number[][]} prerequisites
  4.  * @return {number[]}
  5.  */
  6. var findOrder = 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 ans = [];
  22.   while (queue.length) {
  23.     const selected = queue.shift();
  24.     // cnt++;
  25.     ans.push(selected);
  26.     const toEnQueue = map[selected];//当前课程的后续课程
  27.     if (toEnQueue && toEnQueue.length) {
  28.       for (let i = 0; i < toEnQueue.length; i++) {
  29.         inDegree[toEnQueue[i]]--;
  30.         if (inDegree[toEnQueue[i]] == 0) {
  31.           queue.push(toEnQueue[i])
  32.         }
  33.       }
  34.     }
  35.   }
  36.   if (ans.length == numCourses) return ans;
  37.   return [];
  38. }