朝花夕拾

课程表

5 min read

题目描述

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

思路&js代码

1、广度优先遍历

var canFinish = function (numCourses, prerequisites) {
    const dependsArr = new Array(numCourses).fill(0); // 每个课程的依赖的数量
    const map = {};                                 // 邻接表，存储 课程以及依赖该课程的课程
    for (let i = 0; i < prerequisites.length; i++) {
        const [a, b] = prerequisites[i]
        dependsArr[a]++;              // 求课的初始入度值
        map[b] = map[b] ? [...map[b], a] : [a]
    }
 
    const queue = []; // 所有已经没有依赖的课程
    for (let i = 0; i < dependsArr.length; i++) { // 所有入度为0的课入列
        if (dependsArr[i] == 0) queue.push(i);
    }
 
    let count = 0;
    while (queue.length) {
        const selected = queue.shift();           // 当前选的课，出列
        count++;                                  // 选课数+1
        const nextCourses = map[selected];          // 获取这门课对应的后续课
        if (!nextCourses || !nextCourses.length) continue // 没有后续课
        // 确实有后续课
        for (let i = 0; i < nextCourses.length; i++) {
            dependsArr[nextCourses[i]]--;             // 依赖它的后续课的入度-1
            if (dependsArr[nextCourses[i]] == 0) {    // 如果因此减为0，入列
                queue.push(nextCourses[i]);
            }
        }
 
    }
    return count == numCourses; // 选了的课等于总课数，true，否则false
};

2、深度优先遍历

对于每个节点 x，都定义三种颜色值（状态值）：

0：节点 x 尚未被访问到。 1：节点 x 正在访问中，dfs(x) 尚未结束。 2：节点 x 已经完全访问完毕，dfs(x) 已返回。

⚠误区：不能只用两种状态表示节点「没有访问过」和「访问过」。例如上图，我们先 dfs(0)，再 dfs(1)，此时 1 的邻居 0 已经访问过，但这并不能表示此时就找到了环。

算法流程：

  1. 建图：把每个 prerequisites[i]=[a,b] 看成一条有向边 b→a，构建一个有向图 g。
  2. 创建长为 numCourses 的颜色数组 colors，所有元素值初始化成 0。
  3. 遍历 colors，如果 colors[i]=0，则调用递归函数 dfs(i)。
  4. 执行 dfs(x)： 1. 首先标记 colors[x]=1，表示节点 x 正在访问中。 2. 然后遍历 x 的邻居 y。如果 colors[y]=1，则找到环，返回 true。如果 colors[y]=0（没有访问过）且 dfs(y) 返回了 true，那么 dfs(x) 也返回 true。 3. 如果没有找到环，那么先标记 colors[x]=2，表示 x 已经完全访问完毕，然后返回 false。
  5. 如果 dfs(i) 返回 true，那么找到了环，返回 false。
  6. 如果遍历完所有节点也没有找到环，返回 true。
var canFinish = function(numCourses, prerequisites) {
    const g = Array.from({ length: numCourses }, () => []);
    for (const [a, b] of prerequisites) {
        g[b].push(a);
    }
 
    const colors = Array(numCourses).fill(0);
    // 返回 true 表示找到了环
    function dfs(x) {
        colors[x] = 1; // x 正在访问中
        for (const y of g[x]) {
            if (colors[y] === 1 || colors[y] === 0 && dfs(y)) {
                return true; // 找到了环
            }
        }
        colors[x] = 2; // x 完全访问完毕
        return false; // 没有找到环
    }
 
    for (let i = 0; i < numCourses; i++) {
        if (colors[i] === 0 && dfs(i)) {
            return false; // 有环
        }
    }
    return true; // 没有环
};

Graph View