1 篇博文 含有标签「拓扑排序」

1、题干​

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

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同

2、解题思路​

题干很长，浓缩下就简单很多：给一个有向图，判定其中是否有环 。总的思路是 BFS 或 DFS 遍历整个图，如果存在环则返回 false，否则返回 true。

• 第一步 ：把先修课程 prerequisites 转换为二维数组，即用二维数组存储图的信息
  • 创建二维数组 edges 来表示先修课程，下标表示课程，内层数组表示先修课程集合
  • edges[i] 中的下标 i 表示课程 i ，edges[i] 表示课程i的先修课程集合
  • edges[i][j] 表示课程 i 的一个先修课程，edges[i][j] 的值是 edges 的一个下标

• 第二步 ：按课程序号从0开始深度遍历edges，判定图中是否存在环

• 第三步 ：以任意课程 c 为起始点深度遍历其先修课程，过程中注意3点：
  • 所有遍历过的节点使用哈希集合 visited 记录，以达到剪枝效果避免超时
  • 当前路径遍历过的节点使用哈希集合 paths 记录，如果当前节点已存在于 paths 中，说明存在环
  • 如果课程 c2 后续路径合法，记得将其从 paths 中移除，以免干扰其他路径遍历（类似回溯中的状态重置）

3、复杂度​

• 时间复杂度: $O(n)$
• 空间复杂度: $O(n)$

4、代码​

var canFinish = function (numCourses, prerequisites) {
    // 1、把先修课程`prerequisites`转换为二维数组表示的图
    const edges = new Array(numCourses).fill(0).map(() => []);
    for (let p of prerequisites) edges[p[1]].push(p[0]);

    // 以课程c为起始点，深度遍历所有先修课程
    const visited = new Set();
    function dfs(c, paths) {
        if (visited.has(c)) return false;
        visited.add(c);

        paths.add(c);
        for (const c2 of edges[c]) {
            if (paths.has(c2) || dfs(c2, paths)) return true;
            paths.delete(c2);
        }

        return false;
    }

    // 2、按课程序号从0开始深度遍历`edges`，判定图中是否存在环
    for (let i = 0; i < edges.length; i++) {
        if (dfs(i, new Set())) return false;
    }

    return true;
};