算法图解

拓扑排序是对DAG（有向无环图）上的节点进行排序。
拓扑排序最经典的算法是Kahn算法。首先，先拿出所有入度为0的点排在前面，并在原图中将它们删除：
v2-25e1fb13a53e9dcec5cbb03c29bf7276_1440w.jpg
v2-13e4ae893d5c542b0f5ebb7d75bb09f8_1440w.jpg
v2-9605d775ee870310fb3dc5168b05d868_1440w.jpg

代码实现

  1. /**
  2.  * @param {number} numCourses
  3.  * @param {number[][]} prerequisites 邻接二维数组
  4.  * @return {boolean}
  5.  */
  6. var canFinish = function (numCourses, prerequisites) {
  7.     // 入度数组
  8.     const inDegree = new Array(numCourses).fill(0);
  9.     // 邻接表
  10.     const map = {};
  11.     for (let i = 0; i < prerequisites.length; i++) {
  12.         // 求课的初始入度值
  13.         inDegree[prerequisites[i][0]]++;
  14.         // 当前课已经存在于邻接表
  15.         if (map[prerequisites[i][1]]) {
  16.             // 添加依赖它的后续课
  17.             map[prerequisites[i][1]].push(prerequisites[i][0]);
  18.         } else {
  19.             // 当前课不存在于邻接表
  20.             map[prerequisites[i][1]] = [prerequisites[i][0]];
  21.         }
  22.     }
  23.     const queue = [];
  24.     // 所有入度为0的课入列
  25.     for (let i = 0; i < inDegree.length; i++) {
  26.         if (inDegree[i] == 0) queue.push(i);
  27.     }
  28.     let count = 0;
  29.     while (queue.length) {
  30.         // 当前选的课，出列
  31.         const selected = queue.shift();
  32.         // 选课数+1
  33.         count++;
  34.         // 获取这门课对应的后续课
  35.         const toEnQueue = map[selected];
  36.         // 确实有后续课
  37.         if (toEnQueue && toEnQueue.length) {
  38.             for (let i = 0; i < toEnQueue.length; i++) {
  39.                 // 依赖它的后续课的入度-1
  40.                 inDegree[toEnQueue[i]]--;
  41.                 // 如果因此减为0，入列
  42.                 if (inDegree[toEnQueue[i]] == 0) {
  43.                     queue.push(toEnQueue[i]);
  44.                 }
  45.             }
  46.         }
  47.     }
  48.     // 选了的课等于总课数，true，否则false
  49.     return count == numCourses;
  50. };
  52. let numCourses = 2, prerequisites = [[1,0],[2,1]];
  53. let res = canFinish(numCourses, prerequisites);
  54. console.log(res);

返回值为是否成功进行拓扑排序，也即是否存在环。也就是说拓扑排序是可以用来简单地判环的。有时会要求输出字典序最小的方案这时把queue改成priority_queue即可，复杂度会多一个log。