不关心"距离"或"权值之和"，只关心一堆有先后依赖关系的任务，应该按什么顺序执行才不会违反任何一条依赖。
给定一张有向无环图（Directed Acyclic Graph，简称 DAG），把所有顶点排成一个线性顺序，使得对于图中的每一条有向边 u → v，u 在排列中都出现在 v 的前面——这样的排列就叫拓扑排序。
最经典的场景是"选课依赖"：某些课程要求先修完另一些课程才能选（比如"数据结构"要求先学完"程序设计基础"）。把每门课当成一个顶点，"先修关系"画成有向边，拓扑排序算出来的顺序，就是一种不违反任何先修要求的合法选课顺序。同样的模型也能用于任务调度、编译时的模块依赖顺序等场景。
每个顶点的入度是指有多少条边指向它——对应到选课场景，就是"这门课还有几门先修课没有安排"。入度为 0 的顶点，意味着它没有任何未完成的前置依赖，可以立刻安排。Kahn 算法用一个队列反复做这件事：
| 步骤 | 做什么 |
|---|---|
| ① 统计入度 | 遍历所有边，统计每个顶点的入度 |
| ② 初始化队列 | 把所有入度为 0 的顶点放入队列 |
| ③ 反复处理 | 每次弹出队首顶点 u，加入拓扑序结果；把 u 指向的每个顶点 v 的入度减 1，如果减到 0 就把 v 入队 |
| ④ 结束 | 队列为空时算法结束，此时拓扑序结果里的顶点顺序，就是一种合法的拓扑排序 |
假设有 4 门课 A B C D：A 和 B 都是 C 的先修课，C 又是 D 的先修课（对应边：A→C，B→C，C→D）：
A=0，B=0（都没有先修课），C=2（依赖 A 和 B），D=1（依赖 C）。| 队列（处理前） | 弹出 | 更新入度 | 拓扑序结果 |
|---|---|---|---|
| [A, B] | A | C 的入度 2→1（还不能入队） | A |
| [B] | B | C 的入度 1→0，C 入队 | A, B |
| [C] | C | D 的入度 1→0，D 入队 | A, B, C |
| [D] | D | （D 没有指向任何点） | A, B, C, D |
A, B, C, D——检查一下三条边：A→C（A 在 C 前面 ✓），B→C（B 在 C 前面 ✓），C→D（C 在 D 前面 ✓），全部满足。如果一开始队列里 B 排在 A 前面，得到的结果会是 B, A, C, D——同样合法，这正是 ① 提到的"拓扑序通常不唯一"。| 1 | vector<int> adj[MAXN]; // adj[u]：u 指向的所有点 |
| 2 | int inDeg[MAXN]; // 每个点的入度 |
| 3 | |
| 4 | vector<int> TopoSort(int n) // 返回拓扑序；若长度小于 n，说明图中有环（见 ⑥） |
| 5 | { |
| 6 | queue<int> q; |
| 7 | for (int i = 1; i <= n; i++) |
| 8 | if (inDeg[i] == 0) q.push(i); // ★ 入度为 0 的点先入队 |
| 9 | |
| 10 | vector<int> order; |
| 11 | while (!q.empty()) |
| 12 | { |
| 13 | int u = q.front(); q.pop(); |
| 14 | order.push_back(u); |
| 15 | for (int v : adj[u]) |
| 16 | { |
| 17 | if (--inDeg[v] == 0) q.push(v); // 依赖减少 1，减到 0 就可以安排了 |
| 18 | } |
| 19 | } |
| 20 | return order; |
| 21 | } |
统计入度需要遍历所有边，O(E)；每个顶点入队、出队各一次，O(V)；每条边在"更新入度"时被处理一次，O(E)。总时间复杂度 O(V+E)，和 BFS 是同一量级。
X→Y→Z→X），环上的每个点入度都至少是 1，永远不会被减到 0，也就永远不会入队——这些点会被"晾在一边"，最终 order 的长度会小于 n。判断"图中有没有环"，只需要检查 order.size() == n 是否成立：不成立就说明存在环，根本不存在合法的拓扑排序（对应"选课依赖"的场景，就是几门课互相要求对方先修，谁也没法先上）。queue 的实现细节差异）都可能给出不同但同样合法的顺序。判断对错应该去检查"每条边是否都满足方向要求"，而不是去比较是否和某个特定顺序完全一致。u→v，inDeg[v]++），如果建图时漏加了某条边，或者多组数据之间忘记把 inDeg 数组重新清零，统计出来的入度会不准确，进而导致初始队列里该有的点没入队、或者不该有的点提前入队。