LeetCode 207. 课程表：拓扑排序与有向图中的环检测

课程表（LeetCode 207，Medium）是图算法的转折点：在这之前（本库《岛屿数量》），图的问题用 DFS/BFS「遍历」就够；这道题引入了有向图与依赖关系——课程之间有先修要求，问能否安排出修课顺序。它的本质是：有向图中是否存在环——无环则有解（拓扑排序），有环则无解。拓扑排序是「处理依赖关系的通用算法」：任务调度、构建系统（make）、包管理器的依赖解析、本站文章的发布依赖——底层都是它。本篇讲清两条经典路线。

手绘信息图：拓扑排序与课程表问题

路线一：入度表 + BFS（Kahn 算法）

Kahn 算法的思想极其直观：每次选修「没有先修要求」的课程（入度为 0 的节点），修完后它解锁的后续课程入度减一，减到零的继续选修——选不完（有课的入度永远降不到零）就说明存在环。实现四步：建图与统计入度（graph[b].append(a) 表示 b 是 a 的先修，indeg[a] += 1）；入度为 0 的课程入队；BFS 循环：出队一门课，计数器加一，把它的每门后续课入度减一，减到零的入队；判定：出队总数等于课程数 → 无环可完成；少于课程数 → 有环（剩下的课程互相依赖成环，永远等不到先修）。

from collections import deque

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    graph = [[] for _ in range(num_courses)]
    indeg = [0] * num_courses
    for a, b in prerequisites:          # [a, b]: 先修 b 才能修 a
        graph[b].append(a)
        indeg[a] += 1
    queue = deque(i for i in range(num_courses) if indeg[i] == 0)
    taken = 0
    while queue:
        node = queue.popleft()
        taken += 1
        for nxt in graph[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                queue.append(nxt)
    return taken == num_courses

时间空间 O(V+E)。Kahn 的额外礼物：BFS 的出队顺序本身就是一个合法的拓扑序（LeetCode 210 要求输出顺序，Kahn 免费给出）。

路线二：DFS 三色标记——递归视角的环检测

DFS 路线的思想：从任意节点出发做 DFS，「正在访问」的节点再次被遇到 = 找到了环。实现用三色标记：白色（未访问）、灰色（当前递归栈中——正在被访问）、黑色（已完成——它的所有后续都已探明无环）。DFS 每个节点：白→灰；遍历其后续——遇到灰色（递归栈中的节点）即发现环，返回 False；遇到黑色直接跳过（已验证安全）；遍历完毕该节点转黑（确认无环）。任一 DFS 分支发现环则整体返回 False。两条路线的取舍：只要判环——两者等价，DFS 递归写起来更顺手（注意课程数大时的递归深度限制，Python 需要 sys.setrecursionlimit 或改迭代）；需要输出拓扑序——Kahn 天然给出，DFS 也行（节点转黑时压栈，逆序即拓扑序）；需要处理大规模图——Kahn 的迭代形态更稳（无递归爆栈风险）。共同的纪律：邻接表的建图方向要和入度统计一致——[a, b] 表示 b 先于 a，建图方向写反是本题最常见的静默 bug（对拍或小例验证，本库的本地跑通纪律再次生效）。

拓扑排序的产业延伸：依赖关系的通用算法

拓扑排序的产业价值远超一道题——一切「依赖关系的顺序化」都是它。构建系统：make 与现代构建工具的任务依赖（改了一个文件，哪些目标需要重建、按什么顺序重建——依赖图 + 拓扑排序）；包管理器：npm/pip 的依赖解析（安装顺序的确定、循环依赖的报错——「Circular dependency detected」的报错背后就是环检测）；任务调度：工作流引擎的任务编排（本站文章的发布依赖、数据管道的 ETL 顺序）；编译顺序：模块间的依赖编译。延伸的进阶话题也顺带一提：带权依赖图的关键路径（最长路——项目工期的关键链分析）、以及「部分排序」的稳定性（拓扑序不唯一——满足依赖的顺序有无穷多种，这也是为什么构建工具要自己定义「稳定的排序规则」）。一句产业总结：只要你的系统里出现了「A 完成后才能做 B」的表述，拓扑排序就该出现在你的工具箱里。

建图方向的「对拍」验证与 DFS 迭代版

本题最容易犯的「静默 bug」是建图方向写反，用一个小例子做对拍验证。正确语义：prerequisites = [[1, 0]] 表示「先修 0 才能修 1」——依赖边是 0 → 1（修完 0 解锁 1），入度统计 indeg[1] += 1。方向写反的症状：graph[a].append(b) + indeg[b] += 1 的错误版本，在 [[1,0]] 上会输出什么？入度：indeg[0]=1（错！），初始队列只有课程 1——出队 1，无后续——taken=1 ≠ 2 → 判定有环——正确无环的输入被判「有环」，症状是「明明能修完却说不行」。小例对拍：拿 2 门课、1 条先修的例子手工推一遍期望输出，与代码对照——30 秒发现方向反了。DFS 迭代版（防递归深度）：用显式栈 + 状态表（0 白 1 灰 2 黑），入栈时标灰、所有后续处理完出栈时标黑；「灰色遇灰色」的环检测在迭代版里对应「弹到一半的状态节点再次入栈」的检查——迭代的 DFS 比递归版代码啰嗦，但大图（课程数上万）的递归深度限制是真实风险（Python 默认递归上限 1000——10 万节点的图必爆），图论题的递归与迭代选择，是工程素养的一部分。

拓扑排序的「唯一性」与字典序最小变体

拓扑序不唯一——但有些场景要求「字典序最小的拓扑序」（LeetCode 269 外星文字典的延伸场景）。实现：把 Kahn 的普通队列换成最小堆——每次取「入度为零的节点中编号最小」的，其余流程不变——O(V log V + E)。为什么需要它：当拓扑序本身是「答案的一部分」（比如任务调度的展示顺序、外星字母表的推断），字典序最小的那个是「确定性的规范答案」——多个合法答案中选规范答案，是系统设计「可测性」的通用需求（答案不唯一就无法自动测试）。外星文字典的完整版（LeetCode 269）值得一提：从外星词典的单词顺序推断字母顺序——相邻单词的首个不同字符给出一条「字母 a 先于字母 b」的有向边，全图拓扑排序即字母表；它的坑（非法情况：前缀悖论「abc」在「ab」之前则无解——环检测的语义化应用）与本篇的环检测同源。拓扑排序家族的完整图景：环检测（本篇）、拓扑序输出（210）、字典序最小（堆变体）、以及外星字典（从数据推边）——一套框架吃下「依赖关系」的全部题型。

拓扑排序的工程陷阱：并发调度与动态依赖

拓扑排序的工程落地有两个教科书不讲的陷阱。陷阱一：并发调度的拓扑——依赖图上的任务能否并发执行？入度为零的任务集合每一层可并发（Kahn 的每一波出队就是一批可并行任务——拓扑排序的「层」就是并行调度的波次）；但实际系统的并发度受资源约束（本库语境的 GPU、连接池），「波次并行 + 资源配额」的调度才是真实形态。陷阱二：动态依赖——运行中新出现的依赖（任务 A 执行中发现需要先跑任务 C）会让静态拓扑序失效——解法是局部的增量重排序（只对新依赖涉及的子图重新拓扑）或任务图的重编译（本库语境里构建系统的增量重算）。第三个陷阱：失败传播策略——依赖链上一个任务失败，下游任务是「跳过」「取消」还是「带降级继续」——Kahn 的框架里这是「失败任务的下游入度永不归零」的自然表达，但业务上的降级语义需要额外设计。工程总结：算法课本上的拓扑排序只回答「有没有序、序是什么」，工程里的拓扑排序要回答「怎么并行、依赖变了怎么办、失败了往哪走」——算法与工程之间隔着的那一层，叫做系统设计。

Kahn 与「动态依赖」的进阶：增量拓扑排序

拓扑排序的工程进阶还有一个方向：增量拓扑排序——图在运行时动态加边/加节点，每次变更后需要维护拓扑序而不重算全图。问题的形态：已有的合法拓扑序 + 一条新边 (u, v)——若违反序（u 在 v 之后），需要局部重排；重排的范围可以限制在「u 与 v 之间的窗口」（Pétri 等的经典算法：受影响的节点是窗口内「可达 v 的」与「被 u 可达的」交集——局部修复而非全图重排）。工程的价值：任务调度系统的动态加任务、构建系统的增量依赖更新——全图重排的 O(V+E) 在大图上每次变更都付不起，增量维护把成本压到变更的局部。实现复杂度的诚实评估：增量拓扑的正确性边界（多边同时加、并发变更的竞争条件）让它的工程难度远高于全量重算——多数系统的务实选择是「重算 + 缓存」，把增量留作规模上限到来时的优化课题。这个进阶话题的总纲：拓扑排序的「算法课」一小时学完，「系统课」是动态依赖、并发调度、失败传播的三部曲——本篇正文的算法是地基，工程的三部曲是地上的建筑。

小结

这篇收成四条：课程表的本质是有向图环检测——无环则有拓扑序，有环则无解；Kahn 算法用入度表 + BFS，「选入度为零的课，修完减后续的入度」，出队顺序免费给出拓扑序；DFS 三色标记用「灰色遇灰色即有环」在递归视角判环，大规模图需防递归爆栈；拓扑排序是依赖关系的通用算法——构建系统、包管理器、任务调度、发布依赖，底层全是它。图算法的路线至此清晰：遍历（岛屿数量）→ 环检测与排序（本篇）——下一步是带权图的最短路，那是另一个世界。

参考资料

LeetCode 207/210. Course Schedule I & II —— 题目与官方题解（210 要求输出拓扑序）
Kahn, A. B. (1962). Topological sorting of large networks —— Kahn 算法的原始论文
本库前篇：《LeetCode 200. 岛屿数量》—— 图遍历的前置课