题目
LC 207 课程表：你一共需要修
numCourses 门课，课程编号为
0 到
numCourses - 1。先修关系由
prerequisites 给出，
prerequisites[i] = [a, b] 表示
修课程 a 之前必须先修课程 b。判断是否可能修完所有课程。
LC 210 课程表 II：同一张图，如果能修完，返回
任意一种合法的修课顺序；修不完返回空数组。
输入: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出: true（207）；[0,1,2,3] 或 [0,2,1,3] 都合法（1 和 2 互不依赖，可互换）
注意 [0,3,1,2] 不合法 —— 3 必须先修 1、2
输入: numCourses = 2, prerequisites = [[1,0],[0,1]]
输出: false（207）；[]（210）—— 1 等 0、0 等 1，互相等待
先把方向钉死，这是本题第一大坑：
[a, b] 是「修 a 前先修 b」，所以边是
b → a（先修课指向后修课）。画反了不是小事 —— 它决定你后面所有入度、所有顺序的对错。
于是整道题的翻译只有一句话：
修课顺序 = 有向图的拓扑序；能修完 ⇔ 这张图没有环。
剩下的全部内容，就是「判环 + 生成拓扑序」的两台机器：
Kahn（入度表 + 队列） 和
DFS 三色标记。
一、核心洞察：拓扑序与环
一个有向图里，如果能把所有节点排成一条线，使
每条边都从排在前面的点指向排在后面的点，这条线就是
拓扑序。它恰好就是「一种合法的修课顺序」：先修课全部排在依赖它的课之前。
三条基本性质：
- 有拓扑序 ⇔ 图是有向无环图（DAG）。有环 ⇒ 环上的课互相等 ⇒ 无解（返回 false / 空数组）。
- 拓扑序通常不唯一。本文的默认例子
[[1,0],[2,0],[3,1],[3,2]]，[0,1,2,3] 和 [0,2,1,3] 都合法（1 和 2 互不依赖，可以换位置）。
- 孤立课（没有先修也没有后继）永远可以最先修：入度为 0。
求解路线两条，互为镜像：
- Kahn：反复找「入度为 0」的课修掉，修完把它指向的课入度减 1 —— 天然产出拓扑序；
- DFS 三色：沿着边深搜，碰到指回递归栈的边 = 有环；节点完成时追加后序，后序反转 = 拓扑序。
二、Kahn 算法：入度表 + 队列
入度 = 一门课「还有几门先修没修完」。入度 0 = 现在就能修。Kahn 的全部动作就是：
修掉所有 0 入度的课，并松开它们的后继。
from collections import deque
def canFinish(numCourses, prerequisites):
adj = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for a, b in prerequisites:
adj[b].append(a) # 先修 b → 后修 a
indegree[a] += 1
q = deque(v for v in range(numCourses) if indegree[v] == 0)
order = []
while q:
cur = q.popleft()
order.append(cur) # 出队顺序就是拓扑序
for nxt in adj[cur]:
indegree[nxt] -= 1
if indegree[nxt] == 0: # 入度减到 0 才能修
q.append(nxt)
return len(order) == numCourses # 207 的答案；210 直接返回 order（不足则 []）
判据一句话：
出队数量 == numCourses ⇔ 没有环。如果只剩环（或等环）的课，它们的入度永远减不到 0，队列提前枯竭，
len(order) < numCourses。
三、DFS 三色标记：白、灰、黑，和灰色回边
换一台机器：给每个节点三种颜色 ——
- 白（0）：还没访问过；
- 灰（1）：正在递归栈里（进了它、还没探完它的所有后继）；
- 黑（2）：已确认安全（后继全部处理完，且从它出发到不了环）。
沿边深搜：碰到
白就推进去；碰到
黑直接跳过（那条路已经验过安全）；碰到
灰 —— 说明这条边指回了当前递归栈里的祖先，
环被抓住。
def canFinish_dfs(numCourses, prerequisites):
adj = [[] for _ in range(numCourses)]
for a, b in prerequisites:
adj[b].append(a)
color = [0] * numCourses # 0 白 / 1 灰 / 2 黑
order = [] # 后序
def dfs(v):
color[v] = 1 # 白 → 灰
for nxt in adj[v]:
if color[nxt] == 1: # 灰色回边 = 环
return False
if color[nxt] == 0 and not dfs(nxt):
return False
color[v] = 2 # 灰 → 黑
order.append(v) # 后序：把它追加在「所有后继之后」
return True
for v in range(numCourses):
if color[v] == 0 and not dfs(v):
return False
return True # 210 的答案 = order[::-1]
两个要点：
- 必须区分灰和黑。只用一个
visited 布尔数组会把「黑邻居（安全汇合）」也当成环，误报；
- 后序反转才是拓扑序。后序的追加时机是「所有后继处理完之后」—— 所以先修课自然排在后面，反转后翻到前面。默认例题里后序是
[3,1,2,0]，反转 [0,2,1,3] 就是答案。
对照来看：
Kahn 给 [0,1,2,3]，DFS 给 [0,2,1,3] —— 都对。拓扑序不唯一，两台机器只是「挑了不同的合法线」。
四、动画怎么看
动画一（
algo-viz--lc207）：
Kahn。上方是课程图（圆点 = 课程，箭头 = 先修 → 后修，
右上角小圆 = 当前入度）；下方两行分别是
队列（0 入度的课）和
顺序 order（已修完的课）。盯住三件事：0 入度的课怎么第一时间全部进队列、每修完一门课它的后继入度 −1（
角标当场变小）、以及
入度减到 0 的课才入队。最后
order 满员 = 能修完。
动画二（
algo-viz--lc207dfs）：
DFS 三色。同一张图：白色 = 没访问、灰色 = 递归栈里、黑色 = 已确认安全；左下的
递归栈就是当前的「灰色路径」，右下的
后序 post 是节点变黑时追加的顺序。盯住两件事：
灰 → 黑发生在「后继全处理完」时，以及（有环的图上）
灰色回边会被描红 —— 那就是环。跑完
post 反转就是拓扑序。
五、完整推演表
动画一（Kahn）：
numCourses = 4，
prerequisites = [[1,0],[2,0],[3,1],[3,2]]，即边
0→1、0→2、1→3、2→3，初始入度
[0,1,1,2]。
关键细节：
3 有两个先修（
1 和
2），要
等两个都修完入度才会减到 0 —— 这就是「入度 = 还有几门先修没修」的字面执行。
动画二（DFS 三色）：同一张图，递归顺序
0 → 1 → 3 → 2：
两个对照点：
2 探到
3 时它是
黑的 —— 跳过而不是报环；真正报环的情形是「探到的邻居是
灰」（还在栈里）。
六、Java 版
class Solution {
// Kahn：入度表 + 队列
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
int[] indegree = new int[numCourses];
for (int[] p : prerequisites) {
adj.get(p[1]).add(p[0]); // 先修 p[1] → 后修 p[0]
indegree[p[0]]++;
}
Deque<Integer> queue = new ArrayDeque<>();
for (int v = 0; v < numCourses; v++) {
if (indegree[v] == 0) queue.offer(v);
}
int done = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
done++;
for (int nxt : adj.get(cur)) {
if (--indegree[nxt] == 0) queue.offer(nxt);
}
}
return done == numCourses;
}
}
class Solution {
// DFS 三色：0 白 / 1 灰 / 2 黑
private List<List<Integer>> adj;
private int[] color;
public boolean canFinish(int numCourses, int[][] prerequisites) {
adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
for (int[] p : prerequisites) adj.get(p[1]).add(p[0]);
color = new int[numCourses];
for (int v = 0; v < numCourses; v++) {
if (color[v] == 0 && !dfs(v)) return false;
}
return true;
}
private boolean dfs(int v) {
color[v] = 1;
for (int nxt : adj.get(v)) {
if (color[nxt] == 1) return false; // 灰色回边 = 环
if (color[nxt] == 0 && !dfs(nxt)) return false;
}
color[v] = 2;
return true;
}
}
Java 专属注意点：递归版 DFS 的深度最坏是
O(V)（一条链），
V = 2000 级没事，更大就用
显式栈的迭代版；
210 要在
dfs 里再维护一个
post 列表，节点变黑时
post.add(v)，最后
Collections.reverse(post)。
七、同族题：210 / 269 / 310 / 802 / 1203 / 444
207 只是「拓扑排序」这一族的入口，换个包装就是一条完整题链：
- LC 210 课程表 II：本题的返序版 —— 把 Kahn 的出队顺序（或 DFS 的后序反转）直接返回；
- LC 269 火星词典（会员）：从相邻单词的第一个不同字母建出字母间的偏序边，再做拓扑排序 —— 难点在建图，不在排序；
- LC 310 最小高度树：无向图里反复剥掉「度为 1」的叶子（和 Kahn 剥入度是同一种思想），最后剩下的 1~2 个点就是答案；
- LC 802 找到最终安全状态：反向图上剥「出度为 0」的点，剥不掉的（在环上或等环）就是不安全 —— Kahn 的镜像；
- LC 1203 项目管理：两次拓扑排序 —— 组内排序 + 组间排序；
- LC 444 序列重建（会员）：判断拓扑序是否唯一 —— 队列里同时有 2 个以上 0 入度点就说明有分支，顺序不唯一。
把它们排成一列看：
拓扑排序的模板永远是「算入度/出度 + 反复剥 0 度点（或 DFS 三色）」；剩下的差别只在「边从哪来」（先修关系 / 字母序 / 反向图）和「剥到最后返回什么」。
八、边界情况
- 自环：
[[0,0]] —— 课程等自己，入度永远 ≥ 1，返回 false；
- 重边：
[[1,0],[1,0]] —— 入度被记成 2，被 0 松弛两次才到 0，结果仍正确（但要知道这个行为）；
- 孤立课：没有先修也没有后继，入度 0 直接修，不影响结果；
numCourses = 1、无先修：返回 true，顺序 [0]；- 空
prerequisites：全部入度 0，顺序 [0,1,...,n-1] 本身就是一个合法拓扑序；
- 多个连通块：Kahn 天然处理（入队所有 0 入度点）；DFS 要在外层循环里对每个未访问点各起一次；
- 环上挂着树枝：树枝上的课也被环卡住（等环里的先修），Kahn 里它们的入度同样减不到 0 —— 判环看的是出队总数，不是「有没有节点在环里」的直接检测。
九、复杂度
V = numCourses、
E = prerequisites.length。建图
O(E)，每个节点、每条边恰好被处理一次。剪枝提前退出（发现环立刻返回）不会改变最坏复杂度。
十、常见坑
- 方向画反：
[a, b] 是 b → a（先修 → 后修）。画成 a → b 的话，拓扑序会整个反过来。
- Kahn 简化过头：只
cur 出队却忘了给后继减入度，或者没判断「减到 0 才入队」—— 入度还是正数的课被塞进队列，顺序直接错。
- 判环用「队列空」：所有课修完队列也会空。判据是 出队数量 == numCourses。
- DFS 只用一个
visited 布尔值：没有灰/黑之分，遇到「黑邻居（安全汇合）」也会误报环。必须三色。
- 后序忘了反转：
post.append(v) 的顺序是「后继在前」，直接返回就是反的拓扑序。
- 递归深度：链形图最坏递归
O(V)，大图换显式栈迭代版（或者直接 Kahn，天然无递归）。
- 210 有环时返回了什么：Kahn 里
order 只装了一半 —— 必须检查「len(order) == numCourses」再返回，否则返回残缺顺序。
- 重复边让入度变多：
[[1,0],[1,0]] 会把 1 的入度记成 2（不影响正确性，但要心里有数）；如果用 set 建图，行为会变，别混着写。
- 外层循环漏起点：DFS 版只从
0 开始，会漏掉其它连通块 —— 要对每个未访问节点各起一次 DFS。
- 以为拓扑序唯一：默认例子就有两个合法答案；要「唯一性判定」那是 LC 444 的追问。
十一、面试怎么答
第一段 · 骨架：这题是把「能不能修完」翻译成「有向图有没有环」。先用
[a, b] ⇒ 边
b → a 建图，然后二选一：Kahn 反复剥 0 入度的课、数出队数量；或 DFS 三色，遇见灰色回边就是环。两者都是
O(V + E)。
第二段 · 主动补 210（
这段是区分度所在）：Kahn 的出队顺序天然是一个拓扑序；DFS 则要把
后序反转。顺带指出
拓扑序不唯一（默认例子
[0,1,2,3] 与
[0,2,1,3] 都对），说明你理解的是「一个」合法序而不是唯一解。
第三段 · 追问连接：判唯一性 → LC 444（队列里同层多个 0 入度点 = 不唯一）；建图本身是难点 → LC 269 火星词典；无向图版「剥叶子」 → LC 310；反向图剥出度 → LC 802。
追问连跳：
- 要
返序 → LC 210，Kahn 直接返回 or DFS 后序反转；
- 要
判唯一 → LC 444，看队列是否同时有多个候选；
- 要
从字母对建图再排序 → LC 269，先处理「前一个词是后一个词前缀」的非法情形；
- 要
剥叶子求中心 → LC 310；
- 要
安全节点 → LC 802，反向图 + 剥出度。
一句话收尾：「课程表只有一句话 ——
修课顺序 = 拓扑序，能修完 = 无环；Kahn 剥入度、DFS 认灰边，是这句话的两台等价机器。」
结语
207 的全部难度浓缩在一个翻译里：
先修关系是有向边，修课顺序是拓扑序，环 = 永远修不完。Kahn 用入度表把「现在能修的课」显式排成队列，DFS 用三种颜色把「还没探完的路径」显式画成栈 —— 两条路都通向同一句判据：剥完（或走完）所有节点就没有环。真正拉开差距的，是
方向别画反、灰黑要分清、后序记得翻这三件小事。
下一篇见。