topological-sort · 拓扑排序

拓扑排序：Kahn 与 DFS

一堆任务彼此存在先后依赖：编译单元 a 依赖 b、课程「数据结构」要先修「程序设计」、spreadsheet 里某格依赖另一格。把它们画成有向图（边 $u\to v$ =「u 必须排在 v 前面」）,topological sort 就是把所有节点排成一条线、让每一条边都从前指向后。本系列从拓扑序的定义与「有环则无解」讲起，再单步运行两种经典算法：Kahn（按 in-degree 一层层剥）与 DFS（后序完成、逆序即拓扑序），并看它们如何顺带把图里的环检测出来。

本页是最短路径 / 最小生成树 / 树分解所在 graph 系列的一员；DAG 上的递推可延伸到动态规划。

1 · 定义：把 DAG 排成一条线

给一张有向图，把全部节点排成一个线性序列 $v_1, v_2, \dots , v_n$ ，使得对每一条边 $u\to v$ ,u 都排在 v 前面。这个序列就叫一个 topological order。直觉：边 $u\to v$ 读作「要先有 u 才能有 v」（u 是 v 的前置依赖），那把它们排成线后，所有箭头都该一致地向后指，不能回头。

必须是 DAG（无环）才有拓扑序。「有向」给出方向（谁在前），「无环 (acyclic)」保证这个先后关系不自相矛盾。一旦图里有一个有向环 $a\to b\to c\to a$ ，就出现「a 要排在 b 前、b 要排在 c 前、c 又要排在 a 前」的循环依赖——任何线性顺序都无法同时满足，不存在拓扑序。

拓扑序通常不唯一。上面这张图里，A B C D E F 是一个合法序；但 A C E B D F 同样合法（B、C 谁先都行，只要各自排在依赖它们的节点之前）。节点之间只有偏序 (partial order) 关系——只有被边直接或间接连起来的两点才有强制先后，互不可达的两点（如 B 与 E）顺序自由。拓扑排序就是把这种偏序补全成一个合法的全序。

有环 = 无解，但「跑不出完整序列」恰好能用来检测环。下面两种算法在遇到环时都不会硬排，而是停在那里并报告:Kahn 会发现「还有节点没输出，但已经没有入度为 0 的节点可取」；DFS 会探到一条指回「正在递归栈上」的节点的边 (back edge)。这使拓扑排序天然兼任环检测器。

2 · Kahn 算法：按 in-degree，一层层剥

给每个节点记一个 in-degree（入度）= 指向它的边数 = 它尚未满足的前置依赖数。入度为 0 的节点没有任何未满足的前置，现在就能输出。输出它、把它从图里删掉，它的每条出边 $u\to v$ 就让 v 少了一个前置 (in-degree[v] -= 1)；任何因此降到 0 的节点，轮到它了。

**其一，**算出所有节点的 in-degree，把入度为 0 的节点放进一个队列。
**其二，**从队列取出一个节点 u,追加到输出序列。
**其三，**对 u 的每条出边 $u\to v$ :in-degree[v] -= 1；若 in-degree[v] 变成 0，把 v 入队。
**其四，**回到第二步，直到队列为空。

选「DAG」单步运行，看入度如何从外圈向内一层层归零、节点被逐个输出。再切到「含环图」：会看到队列提前耗尽、还剩节点的入度卡在 > 0——这些节点正落在环上，图没有拓扑序。

结束 = 队列空。若此时输出序列长度等于节点总数，它就是一个合法拓扑序。每个节点被取出时，它的全部前置都已先被输出（否则入度不会归零），所以「边都从前指向后」自然成立。

队列空但还有节点没输出 → 图有环。剩下的节点入度始终 > 0：它们彼此构成循环依赖，谁也等不到自己的前置被清空。这就是 Kahn 给出的环检测结论——output.length < V 即有环。

3 · DFS 算法：后序完成，逆序即拓扑序

换一个视角：从某个节点出发深度优先地往下走。给节点三种颜色——白（未访问）、灰（正在递归栈上、子树还没探完）、黑（已完成、所有出边都探尽）。关键洞察：一个节点变黑 (finish) 的时刻，意味着它能到达的所有节点都已经先变黑了。所以按 finish 先后收集节点，得到的恰好是逆拓扑序——被依赖的反而先完成；把它整个翻转，就是拓扑序。

dfs(u): 把 u 染灰（压入递归栈）→ 依次看每条出边 $u\to v$ :v 是白就递归 dfs(v)（树边）;v 是黑说明那棵子树早探完了，跳过 → 出边都看完后，把 u 染黑、追加到 finished 列表。全部 dfs 跑完，finished 逆序就是拓扑序。

遇到指向「灰」节点的边 = back edge = 环。v 还是灰色，说明 v 仍在当前递归栈上、是 u 的祖先; $u\to v$ 把路径绕回了祖先，正好构成一个有向环。一旦探到 back edge，图就没有拓扑序——这是 DFS 版的环检测。切到「含环图」即可看到这一刻。

节点下方的数字 = 它第几个 finish（变黑的先后）。看完 DAG 后留意：把 finish 顺序倒过来，正好让每条边都从前指向后。

**为什么 finish 顺序是逆拓扑序？**对任意边 $u\to v$ ：递归到 u 时 v 要么是白（会先被 dfs(v) 探完、先 finish），要么是黑（早就 finish 了）——无论哪种，v 总在 u 之前 finish。于是 finished 列表里 v 排在 u 前；翻转后 u 在 v 前，正是拓扑序要求的方向。

4 · 两种算法对比 · 应用

	Kahn （BFS · 入度）	DFS （后序逆序）
核心数据	in-degree 数组 + 队列	三色标记 + 递归栈
产出方向	直接得到拓扑序	得逆拓扑序，翻转一次
环检测	`output.length < V`	探到 back edge （指向灰节点）
复杂度	$O(V + E)$ ，每个节点、每条边各处理一次	$O(V + E)$ ，每个节点、每条边各处理一次
顺手附赠	可分「层」（同时入队的是同一拨）	同一趟 DFS 可求强连通分量等

它真实跑在哪里。 构建系统:make / Bazel / Gradle 按文件依赖图拓扑排序决定编译顺序；循环依赖会被当作错误报出（即环检测）。
包管理器:npm / cargo / pip 解析依赖图、按拓扑序安装，检测到环则拒绝。
任务 / 课程调度：有先后约束的任务编排、课程先修关系（LeetCode「Course Schedule」就是它）。
表格与响应式:spreadsheet 单元格依赖、前端 signals / reactive 系统按拓扑序重算，避免重复或遗漏更新。
编译与数据流：符号 / 类型的解析顺序、构建流水线 stage 排布、Excel 公式求值。

5 · 相关链接

最短路径 · Dijkstra · 本站 graph 系列——同属 graph 系列。DAG 上有了拓扑序，单源最短 / 最长路径可一遍线性 DP 求出（无需 Dijkstra）。
动态规划 · 背包九讲 · 本站 — DAG 上的递推天然按拓扑序进行——拓扑序就是「无后效性」状态转移的计算顺序。
Topological sorting · en.wikipedia.org — Kahn (1962) 与 DFS 两种经典算法、唯一性条件 (Hamiltonian path) 与并行变体的权威综述。
Course Schedule II · leetcode.com — 拓扑排序的标准练习题：给出课程先修关系，求一个合法修课顺序，有环则返回空。