拓扑排序
拓扑排序为有向无环图的全部顶点安排顺序，使每条边都从前面的顶点指向后面的顶点。Kahn 算法不断移除入度为零的源点；DFS 在返回时记录顶点，再反转完成顺序。两者时间均为 O(V + E)，都要拒绝有向环。
课程先修关系就是这种约束：一门课的全部前置课程都完成后，它才可以开始。Kahn 从当前可执行的课程出发；DFS 先沿依赖关系走到底，返回时从结果尾部安排顶点。
拓扑排序如何工作
不变量是：每条有向边 u -> v 都满足 u 在 v 之前。结果不必唯一；两个顶点都没有剩余前置依赖时，除非外部规则另有限制，哪个在前都合法。
Kahn 保存每个顶点的剩余入度。先把所有零入度顶点放入队列，取出一个源点加入答案，再将它每个出边邻居的入度减一。某邻居恰好降到零时入队。如果队列空了而答案未包含全部顶点，剩余图中就存在有向环，并可能包含被环阻塞的下游顶点。
DFS 在调用开始时把顶点标为活动状态，全部出边邻居完成后，才标记结束并追加到完成列表。列表中被依赖方的后继先出现，因此反转它得到拓扑序。指向活动祖先的边说明存在环，不能继续递归。
需要解释失败原因时可用 Kahn：剩余图包含环及受它阻塞的任务，适合构建工具。它使用迭代，长依赖链不会耗尽递归栈。已有递归遍历及活动、结束状态时，DFS 也便于集成。
拓扑排序逐步演示
默认 Kahn 示例有六个顶点，边为 A->C、B->C、B->D、C->E、D->E、D->F、E->F。
- 统计入度：
A=0, B=0, C=2, D=1, E=2, F=2。 - 初始化 FIFO 队列
[A, B]。字母顺序只用于固定回放，不是图的额外约束。 - 取出并输出 A。移除
A->C，C 从 2 降为 1，仍不能入队。 - 取出并输出 B。
B->C使 C 从 1 降为 0，C 入队；B->D使 D 从 1 降为 0，D 随后入队。队列[C, D]，输出[A, B]。 - 输出 C。E 从 2 降为 1，仍被阻塞。
- 输出 D。
D->E使 E 降为 0 并入队；D->F使 F 从 2 降为 1。队列[E]。 - 输出 E。
E->F使 F 降为 0，再输出 F。 - 队列空，六个顶点全部输出，返回
[A, B, C, D, E, F]。 - 验证阶段按该顺序排列顶点，检查七条边都向右，再按 DFS 的
[B, D, A, C, E, F]重排并检查，同样通过。若每条边都向右，就不可能沿边回到起点，因此该序列也证明不存在环。
同一张图上，DFS 的完成顺序为 [F, E, C, A, D, B]，反转后得到 [B, D, A, C, E, F]。它与 Kahn 结果不同，但都满足所有依赖。
Kahn 模式可观察 in=k 标记何时降为零并入队；DFS 模式可观察节点等所有后继完成、变绿后才进入完成行。
时间与空间复杂度
| 算法 | 时间 | 辅助空间 | 每条边的工作 |
|---|---|---|---|
| Kahn | O(V + E) | O(V) | 初始化时增加一次入度，处理时减少一次 |
| DFS | O(V + E) | O(V) | 递归遍历时检查一次 |
图本身占 O(V + E)。Kahn 另存入度、队列和输出；DFS 存三态表、完成列表，长链还可能需要 O(V) 个调用帧。它们不是比较排序，不受 O(n log n) 的比较排序下界限制；读取完整邻接表本就需要 O(V + E)。
边界情况
- 单顶点无边：两种算法都返回该顶点。
- 多顶点无边：任何排列都合法，固定规则只让结果可重复。
- 单链：约束决定唯一顺序，每个非首顶点都依赖前一个。
- 不连通 DAG：必须处理所有部分。DFS 需遍历全部顶点的外层循环，只从一个顶点开始只能求可达区域。
- 自环或有向环：无拓扑序。Kahn 留下未处理顶点，DFS 检测到指向活动顶点的边。
常见错误
- 入度为一就入队。一条前置依赖未完成也不能开始，必须降到零。
- 首次看到顶点就按 BFS 习惯标记可用。Kahn 的可用性由剩余入度决定。
- DFS 入口就追加答案。那是先序，可能违反其他前置约束；应返回时追加，再反转。
- 用一个访问位检测 DFS 环。必须区分活动和结束，指向结束节点并不证明有环。
- Kahn 停顿后返回部分列表。必须检查结果长度等于 V，合法前缀不是全图拓扑序。