拓扑排序-课程表系列

leetcode 207 课程表

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

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

例如，先修课程对  [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

拓扑排序

这种在一个图中，互相有依赖关系，需要按照依赖顺序排序输出的问题，就是拓扑排序。拓扑排序除了排序输出之外，还可以验证图中是否有环。比如下面常见的拓扑排序的应用。

• 课程学习的先后顺序
• 相互依赖的文件的编译顺序

拓扑排序的方法

一是 Kahn 算法。二是深度优先遍历

Kahn 算法

个人认为 Kahn 算法还是比较好理解的。首先需要定义 b 依赖与 a，a 要先与 b 执行，那么就是 a->b。
此时 b 的入度是 1，a 的入度是 0。

1. 算法的思路就是首先统计出所有的点的入度，还需要统计所有点的 next 点
2. 然后找到入度为 0 的点，访问它，随后，将该点的所有 next 点的入度都减 1
3. 然后重复 2 这个步骤
4. 直到没有入度为 0 的点为止

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const inDegree = Array(numCourses).fill(0);
  const adjacent = inDegree.map(() => []);

  for (const [cur, pre] of prerequisites) {
    // pre -> cur
    inDegree[cur] += 1;
    adjacent[pre].push(cur);
  }

  // 找到所有入度为0的课程
  const queue = [];
  for (let i = 0; i < inDegree.length; i++) {
    if (inDegree[i] === 0) {
      queue.push(i);
    }
  }

  const list = [];
  // 遍历入度为0的课程，入度为0，则加入list, 并将它的临接课程入度-1
  while (queue.length) {
    const cur = queue.shift();
    list.push(cur);

    // 将当前课程的所有后序课程的入度减1，如果后序课程的入度为0，则加入list
    adjacent[cur].forEach((next) => {
      inDegree[next]--;
      if (inDegree[next] === 0) {
        queue.push(next);
      }
    });
  }

  // 最后验证一下，是否所有的课程都学完了
  return list.length === numCourses;
}

dfs 深度优先遍历

深度优先遍历，也是解决拓扑排序的常用办法。其思路就是沿着一个点，一直往前找它的前置点，直到没有前置的点了，就是找到头了。此时就可以回溯访问了（从外到内探索，从内到外回溯访问）。
需要注意的是，需要记录点的状态，未访问｜访问中｜已经访问。

• 如果未访问需要标记未访问中
• 如果是访问中，则说明又访问了一次，存在环
• 如果是已经访问，那么直接返回就可以了;比如(这里和 Kahn 算法是反的，a->b 代表 b 先于 a 执行。a 依赖 b)
  • a->b->c
  • d->b->c
  • 访问完 a 这条链路，b 和 c 就已经访问了。因此再访问 d 这条链路时，就不需要访问 b 和 c 了

function dfs(
  cur: number,
  pres: number[][],
  visited: number[],
  res: number[]
): boolean {
  if (visited[cur] === 2) {
    // 已经访问过了
    return true;
  } else if (visited[cur] === 1) {
    // 正在访问中，结果又来访问了。出现了环
    return false;
  } else {
    // 设为访问中
    visited[cur] = 1;
    for (let i = 0; i < pres[cur].length; i++) {
      // 访问前置节点
      if (!dfs(pres[cur][i], pres, visited, res)) {
        return false;
      }
    }
    visited[cur] = 2;
    res.push(cur);
    return true;
  }
}

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const visited = Array(numCourses).fill(0); // 0-未访问；1-访问中；2-已经访问
  const pres = visited.map(() => []); // 记录节点的前置节点

  // 统计节点的前置节点
  for (let [cur, pre] of prerequisites) {
    pres[cur].push(pre);
  }
  const res = [];
  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i, pres, visited, res)) {
      return [];
    }
  }
  return res;
}