拓扑排序
图算法 · 有向无环图（DAG）的依赖排序
什么是拓扑排序
有些事情有先后依赖：先修完「高等数学」才能上「概率论」，先编译完 A 库才能链接 B。把这些「谁必须在谁之前」画成一张有向图（边 u→v 表示「u 必须在 v 前」），拓扑排序就是给出一个满足所有依赖的线性顺序——排在前面的绝不依赖后面的。前提是图无环（有环就互相依赖、无解）。
Kahn 算法怎么做
一个直观办法（Kahn 算法）：先数每个点的入度（有多少条边指向它）。入度为 0 的点没有任何前置依赖，可以直接输出；输出它之后，把它「删掉」——它指向的每个后继入度减 1。不断重复「取一个入度 0 的点输出、后继减度」，直到所有点输出完。
下面固定一张 6 个点的 DAG。点「下一步」逐步看：当前取出的入度 0 点琥珀高亮、输出后变绿，它的出边黄色高亮、后继的入度徽标下降——某个后继降到 0 时又成为下一批可输出的点。走到底得到一个合法拓扑序（本图为 C→A→E→B→D→F）。右侧代码随每一步同步高亮。
先数每个点的入度（指向它的边数）
1function topoSort(edges: [number, number][], n: number): number[] {
2 const indeg = Array(n).fill(0);
3 for (const [u, v] of edges) indeg[v]++;
4 const order: number[] = [];
5 const done = Array(n).fill(false);
6 while (order.length < n) {
7 let u = -1;
8 for (let i = 0; i < n; i++)
9 if (!done[i] && indeg[i] === 0) { u = i; break; }
10 if (u === -1) break;
11 done[u] = true;
12 order.push(u);
13 for (const [a, b] of edges) if (a === u) indeg[b]--;
14 }
15 return order;
16}
当前点-
已输出-
剩余6
入度[A]1
入度[B]2
入度[C]0
入度[D]1
入度[E]0
入度[F]3
1 / 14
注意：入度 0 的点可能同时有多个，取哪个都对——拓扑序通常不唯一（这里固定「取下标最小的」让过程确定）。复杂度 O(V + E)：每个点、每条边各处理一次。若某步找不到入度 0 的点但还有点没输出，就说明图里有环，不存在拓扑序。
拓扑排序在哪里用
课程/先修：安排一个不违反先修关系的修课顺序。
构建/编译：按依赖决定模块编译、任务执行顺序（Make、打包器都用它）。
电子表格：单元格公式依赖的重算顺序。也用于检测循环依赖（有环即报错）。
构建/编译：按依赖决定模块编译、任务执行顺序（Make、打包器都用它）。
电子表格：单元格公式依赖的重算顺序。也用于检测循环依赖（有环即报错）。
Kahn 用「入度 + 队列」实现——想复习队列怎么进出，可回看 数据结构 · 队列；想看图怎么存、怎么遍历，回看 数据结构 · 图。