#207. 课程表

• LeetCode：207. 课程表
• 难度：中等
• 归类：图、拓扑排序、广度优先搜索、深度优先搜索
• 主解法：Kahn 拓扑排序

#先给结论

把每门课程看成一个节点。对于先修关系：

[course, prerequisite]

建立有向边：

prerequisite → course

indegree[course] 表示这门课还有多少门先修课没有完成。

Kahn 拓扑排序不断学习入度为 0 的课程，并删除它指向的依赖边：

• 如果最终能处理 numCourses 门课程，图中没有环，可以完成全部课程。
• 如果队列提前为空但仍有课程未处理，剩余依赖形成环，不可能完成。

这题虽然使用队列，但不是求最短路，也不需要按 BFS 层数更新答案。

#题目描述

共有 numCourses 门课程，编号为 0 到 numCourses - 1。

先修关系：

prerequisites[i] = [a, b]

表示学习课程 a 前必须先完成课程 b。判断是否存在一种顺序完成所有课程。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true

可以按 0 → 1 的顺序学习。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false

课程 0 和 1 互相依赖，形成有向环。

题目约束：

• 1 <= numCourses <= 2000。
• 0 <= prerequisites.length <= 5000。
• 每个先修关系恰好包含两个合法课程编号。
• 所有先修课程对互不相同。

#图模型

#边的方向

[a, b] 的含义是“先学 b，才能学 a”，所以自然的执行方向是：

b → a

代码中：

nextCourses[b].push(a)
indegree[a]++

nextCourses[b] 保存完成课程 b 后可能被解锁的课程。

#入度的含义

indegree[a] 是课程 a 尚未满足的先修条件数量。

• 入度为 0：现在就能学习。
• 入度大于 0：至少还有一门先修课没完成。
• 完成一门课程后，它的每个后继课程入度减 1。

入度减到 0 的瞬间，说明该课程所有先修条件都已满足，可以入队。

#为什么问题等价于判断有向环

如果依赖图中存在环：

A → B → C → A

那么学习 A 前要先完成环中的另一门课程，沿环追溯永远找不到可以最先学习的课程。

如果图中没有环，它是有向无环图。任何有限有向无环图都至少存在一个入度为 0 的节点。删除它及其出边后，剩余图仍是有向无环图，可以继续这一过程，直到删除所有节点。

所以：

可以完成所有课程
⇔ 存在拓扑序
⇔ 依赖图没有有向环

#Kahn 算法状态与不变量

维护：

• nextCourses：邻接表，保存每门课程的后继。
• indegree：当前尚未删除的依赖边数量。
• queue：已经满足全部先修条件、等待处理的课程。
• completed：已经从队列中处理的课程数量。

循环过程中保持：

1. 队列中的每门课程当前入度都为 0。
2. 每处理一门课程，就只删除它发出的边。
3. indegree 始终对应尚未处理子图中的真实入度。
4. 同一课程只会在入度第一次降为 0 时入队一次。

#示例推演

考虑：

numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]

图为：

0 → 1 → 3
 \      ↑
  → 2 ──┘

初始入度：

处理过程：

最终 completed === numCourses，所以返回 true。

对于环：

[[1,0],[0,1]]

两个节点初始入度都是 1，队列从一开始就是空的，无法处理任何课程，返回 false。

#算法步骤

1. 创建长度为 numCourses 的邻接表和入度数组。
2. 对每个 [course, prerequisite]：
   • 添加边 prerequisite → course。
   • 增加 course 的入度。
3. 将所有入度为 0 的课程加入队列。
4. 使用头指针依次取出课程：
   • completed++。
   • 将所有后继课程入度减 1。
   • 某个后继入度变为 0 时，将它入队。
5. 返回 completed === numCourses。

#代码实现

原文章的 JavaScript 参考实现来源：JoshCrozier/leetcode-javascript。原实现采用 DFS 判环，本文改为 Kahn BFS，使代码与主解法和正文保持一致；原项目采用 MIT License。

#JavaScript 实现

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
    const nextCourses = Array.from(
        { length: numCourses },
        () => [],
    );
    const indegree = new Array(numCourses).fill(0);

    for (const [course, prerequisite] of prerequisites) {
        nextCourses[prerequisite].push(course);
        indegree[course]++;
    }

    const queue = [];

    for (let course = 0; course < numCourses; course++) {
        if (indegree[course] === 0) {
            queue.push(course);
        }
    }

    let head = 0;
    let completed = 0;

    while (head < queue.length) {
        const prerequisite = queue[head++];
        completed++;

        for (const course of nextCourses[prerequisite]) {
            indegree[course]--;

            if (indegree[course] === 0) {
                queue.push(course);
            }
        }
    }

    return completed === numCourses;
};

使用头指针读取队列，不调用 Array.shift()，避免反复移动数组元素。

#代码与思路对照

#正确性说明

#被处理的顺序一定合法

课程只有在入度变为 0 时才会入队。根据入度定义，此时所有指向它的先修边都已随着对应先修课程的完成而删除。

所以每门出队课程的全部先修课都已处理，出队顺序是一个合法的拓扑序前缀。

#处理全部课程时一定可完成

如果 completed === numCourses，出队顺序包含每一门课程，并且根据上一条性质，每门课程都出现在其所有后继之前。因此存在合法学习顺序，应返回 true。

#未处理全部课程时一定存在环

如果队列为空但仍有未处理课程，剩余子图中的每个节点入度都大于 0。

从任意剩余节点沿一条入边不断向前追溯。剩余节点有限，最终必然重复访问某个节点，形成有向环。环中课程互相等待，无法完成全部课程，应返回 false。

因此算法的返回值与题意完全一致。

#边界与陷阱

• 没有先修关系： 所有课程初始入度为 0，返回 true。
• 孤立课程： 即使不出现在 prerequisites 中，也必须加入初始队列并计入 completed。
• 两节点互相依赖： 两者都无法达到入度 0，返回 false。
• 自依赖： 若出现 [a, a]，课程 a 构成自环，无法完成。
• 边方向： [a, b] 应按执行顺序建立 b → a。
• 入度加在后继： 应执行 indegree[a]++，不是增加 b。
• 入度为零时再入队： 不能在仍有未满足条件时提前处理。
• 不要只检查队列是否曾非空： 局部无环不代表所有课程可完成，必须比较最终处理数量。
• 无需固定层大小： 拓扑排序只关心可处理节点集合，不计算 BFS 层数。
• 避免 shift()： 使用头指针保持线性总时间。

#复杂度分析

设：

• V = numCourses。
• E = prerequisites.length。

建图需要 O(V + E) 时间。每门课程至多入队、出队一次，每条依赖边恰好用于一次入度递减，因此：

• 时间复杂度：O(V + E)。
• 空间复杂度：O(V + E)，用于邻接表、入度数组和队列。

队列数组会保留已经读取的槽位直到函数结束，所以其分配规模为 O(V)，仍包含在上述空间界限内。

#替代解法

#DFS 三色判环

为每个节点维护：

• 0：尚未访问。
• 1：正在当前递归路径中访问。
• 2：已经完成，确认从它出发无环。

DFS 遇到状态 1 的节点时说明存在回边和有向环；遇到状态 2 可以直接复用结果。时间和空间同样是 O(V + E)。

JavaScript 中递归深度受运行环境调用栈限制。虽然本题最多 2000 门课程通常可以运行，迭代式 Kahn 算法没有递归栈风险。

#返回实际课程顺序

本题只返回布尔值。如果要解决 210「课程表 II」，把每次出队课程依次加入答案数组：

• 最终长度为 V：返回该数组。
• 长度小于 V：存在环，返回空数组。

#面试官递进追问

#1.[a, b] 应该建立哪条边？

学习 a 前必须先完成 b，所以按执行顺序建立 b → a。这样完成 b 时才能减少 a 的未满足条件。

#2. 入度为0 在课程语义中表示什么？

表示当前没有任何尚未完成的先修课程，这门课现在可以安全学习。

#3. 为什么存在环时环中节点永远不会入队？

环中每个节点至少有一条来自环内前驱的入边。要删除这条边必须先处理前驱，而前驱又等待环中其他节点，所以没有节点能率先达到入度 0。

#4. 为什么completed === numCourses 可以证明无环？

被处理的每门课程都在所有先修条件满足后出队。如果全部节点都能按这种顺序处理，就已经构造出完整拓扑序；有向环不可能包含在拓扑序中。

#5. 为什么孤立课程也要进入队列？

它没有任何先修课，当然可以完成，而且题目要求完成全部 numCourses 门课程。遗漏它会导致处理数量错误。

#6. 为什么这里不需要按层固定队列长度？

本题不求最少学期数或层级，只要不断处理任意入度为 0 的课程即可。新解锁课程可以直接追加到同一个队列尾部。

#7. BFS 拓扑排序和 DFS 判环如何取舍？

Kahn 算法直接用处理数量判断环，也容易输出拓扑序；DFS 三色法直观对应递归路径上的回边，但要处理递归深度。两者渐进复杂度相同。

#8. 如果动态新增一条先修关系怎么办？

重新运行拓扑排序最直接，成本为 O(V + E)。若需要大量在线更新，就要维护动态拓扑序；新增边可能打破原顺序并产生环，问题明显更复杂。

#常见错误

• 把 [course, prerequisite] 的边方向和入度含义写反。
• 只创建出现在先修数组中的节点，漏掉孤立课程。
• 一门课程尚有多个先修条件时，减少一次入度就提前入队。
• 队列清空就返回 true，没有比较处理节点总数。
• 把拓扑排序误讲成最短路或普通分层 BFS。
• 正文讲 BFS，代码却使用 DFS，导致不变量和实现完全不对应。
• 使用 Array.shift() 却未经分析直接宣称 JavaScript 队列操作为常数时间。
• DFS 只记录“访问过”，没有区分当前递归路径与已经完成。

#可迁移总结

• 依赖建模： 边从前置任务指向后续任务，入度表示未满足前置条件数量。
• 零入度推进： 不断删除当前可执行任务及其出边。
• 处理数量判环： 能处理全部节点等价于存在拓扑序。
• 一句话记忆： 先修课指向课程，零入度课程入队，最终处理数等于课程总数才可完成。

#刷题后自测

先只回答第 1 题，再展开后续问题：

1. 为什么先修关系 [1, 0] 要建立边 0 → 1？

2. 如果一门课有两门先修课，什么时候才能入队？

3. 队列为空但 completed < numCourses 时，剩余图为什么一定有环？

4. 尝试把实现改为 DFS 三色判环，并说明状态 1 与状态 2 的区别。