什么是拓扑排序
拓扑排序（Topological Sorting）把有向无环图（DAG）的所有顶点排成一个线性序列，使得对每条边 u→v，u 都出现在 v 之前。它本质上是把图中的偏序关系变成全序。
三个关键性质：
- 只适用于 DAG：图里有环就不存在合法拓扑序（可以用它做环检测）；
- 结果不唯一：同一张图通常有多种合法拓扑序；
- 语义明确：”u 排在 v 前”对应现实中的依赖关系——先修课、任务依赖、编译顺序。
典型应用：任务调度、课程安排、编译顺序（源文件依赖）、电路设计中的布线顺序、生产调度。
算法一：Kahn（基于入度，BFS）
反复”找出当前入度为 0 的节点”并移除：
- 统计所有节点的入度；
- 入度为 0 的节点入队；
- 出队节点加入结果序列，将其所有后继的入度减 1；
- 入度变为 0 的后继入队；
- 重复直到队列空。若结果节点数 ≠ 总节点数，说明图中有环。
bool topologicalSort(vector<vector<int>>& G, vector<int>& inDegree, int n) {
queue<int> q;
vector<int> res;
for (int i = 0; i < n; i++)
if (inDegree[i] == 0) q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
res.push_back(u);
for (int v : G[u])
if (--inDegree[v] == 0) q.push(v);
}
return res.size() == n; // false 说明有环
}
算法二：DFS 后序
对图做 DFS，递归返回后把当前节点压栈，最终栈的逆序就是拓扑序：
def topological_sort_dfs(graph):
visited = set()
stack = []
def dfs(u):
visited.add(u)
for v in graph.get(u, []):
if v not in visited:
dfs(v)
stack.append(u) # 所有后继处理完才压栈
for u in graph:
if u not in visited:
dfs(u)
return stack[::-1] # 逆序即拓扑序
复杂度
| 算法 | 时间 | 空间 | 特点 |
|---|---|---|---|
| Kahn | O(V+E) | O(V) | 直观、适合动态图、天然支持环检测 |
| DFS | O(V+E) | O(V) | 代码简洁，需要递归（可用三色标记判环） |
实战：课程安排（LeetCode 207）
判断能否完成所有课程，即判断依赖图是否无环——Kahn 版：
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = new List[numCourses];
int[] inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) graph[i] = new ArrayList<>();
for (int[] cp : prerequisites) {
graph[cp[1]].add(cp[0]);
inDegree[cp[0]]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++)
if (inDegree[i] == 0) q.offer(i);
int count = 0;
while (!q.isEmpty()) {
int pre = q.poll();
count++;
for (int cur : graph[pre])
if (--inDegree[cur] == 0) q.offer(cur);
}
return count == numCourses;
}
技巧与常见问题
- 环检测：Kahn 看结果数量，DFS 用三色标记（灰 = 在递归栈中，遇到灰节点即环）；
- 并行任务：同一时刻入度为 0 的节点可以并行处理；
- 字典序最小拓扑序：把 Kahn 的普通队列换成优先队列即可；
- 输出具体课程顺序：LeetCode 210 要求返回顺序，Kahn 的 res 就是答案。
