一、什么是拓扑排序
拓扑排序（Topological Sort） 对有向无环图（DAG）的顶点排成线性序列，使得对每条有向边 (u, v)，u 都排在 v 前面。
典型应用：课程先修关系、编译依赖、任务调度。
Mermaid · 渲染中（下方为源码）
graph LR A[数据结构] --> C[操作系统] B[离散数学] --> C C --> D[编译原理] A --> D D --> E[毕业设计]
合法拓扑序之一：数据结构 → 离散数学 → 操作系统 → 编译原理 → 毕业设计
前提：图必须是 DAG（无环）。有环则不存在拓扑序。
二、两种实现方式
2.1 BFS（Kahn 算法）
不断删除入度为 0 的节点：
public int[] topologicalSort(int n, int[][] edges) {
List<Integer>[] graph = new ArrayList[n];
int[] inDegree = new int[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int[] e : edges) {
graph[e[0]].add(e[1]);
inDegree[e[1]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) queue.offer(i);
}
int[] order = new int[n];
int idx = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
order[idx++] = u;
for (int v : graph[u]) {
inDegree[v]--;
if (inDegree[v] == 0) queue.offer(v);
}
}
// idx < n 说明有环
return idx == n ? order : new int[0];
}- 时间：O(V + E)，空间：O(V + E)
2.2 DFS（后序反转）
DFS 完成时记录节点，最后反转：
public int[] topologicalSortDFS(int n, int[][] edges) {
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int[] e : edges) graph[e[0]].add(e[1]);
int[] state = new int[n]; // 0=未访问, 1=访问中, 2=已完成
Deque<Integer> stack = new ArrayDeque<>();
boolean[] hasCycle = {false};
for (int i = 0; i < n; i++) {
if (state[i] == 0) {
dfs(graph, i, state, stack, hasCycle);
}
}
if (hasCycle[0]) return new int[0];
int[] order = new int[n];
for (int i = 0; i < n; i++) order[i] = stack.pop();
return order;
}
private void dfs(List<Integer>[] graph, int u, int[] state,
Deque<Integer> stack, boolean[] hasCycle) {
state[u] = 1;
for (int v : graph[u]) {
if (state[v] == 1) { hasCycle[0] = true; return; }
if (state[v] == 0) dfs(graph, v, state, stack, hasCycle);
}
state[u] = 2;
stack.push(u);
}三、环检测
| 方法 | 判断依据 |
|---|---|
| BFS（Kahn） | 处理完的节点数 < n → 有环 |
| DFS | 遇到"访问中"的节点 → 有环 |
四、经典应用
4.1 课程表（LeetCode 207/210）
问题：n 门课程，prerequisites[i] = [a, b] 表示学 a 前必须先学 b。能否完成所有课程？
public boolean canFinish(int numCourses, int[][] prerequisites) {
return topologicalSort(numCourses, prerequisites).length == numCourses;
}4.2 外星文字典（LeetCode 269）
从排序的外星词表中推导字母顺序 → 建图 + 拓扑排序。
4.3 编译依赖 / 任务调度
任务 A 依赖 B、C → 边 B→A, C→A
拓扑序 = 合法执行顺序
五、拓扑排序 + DP
在 DAG 上按拓扑序做动态规划：
问题：DAG 中的最长路径。
public int longestPath(int n, int[][] edges, int[] weight) {
List<int[]>[] graph = new ArrayList[n];
int[] inDegree = new int[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int[] e : edges) {
graph[e[0]].add(new int[]{e[1], e[2]});
inDegree[e[1]]++;
}
Queue<Integer> queue = new LinkedList<>();
int[] dist = new int[n];
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) queue.offer(i);
}
while (!queue.isEmpty()) {
int u = queue.poll();
for (int[] edge : graph[u]) {
int v = edge[0], w = edge[1];
dist[v] = Math.max(dist[v], dist[u] + w);
if (--inDegree[v] == 0) queue.offer(v);
}
}
return Arrays.stream(dist).max().getAsInt();
}六、BFS vs DFS 选择
| 维度 | BFS（Kahn） | DFS |
|---|---|---|
| 实现 | 直观（入度） | 递归（后序） |
| 环检测 | 计数 < n | 三色标记 |
| 多解 | 可用优先队列得字典序最小 | 取决于遍历顺序 |
| 适用 | 更常用 | 需要 DFS 序时 |
七、面试常见题
- 🟢 课程表 I（能否完成）
- 🟡 课程表 II（返回顺序）、外星文字典
- 🟠 并行课程（最少学期数）、序列重建
- 🔴 DAG 上最长路径、有向图强连通分量（Tarjan）
八、调试技巧
- 建图方向：
[a, b]表示 b→a（先修 b 才能学 a），别搞反。 - 入度初始化：确保所有边都统计到。
- 环的判断：BFS 结束后
idx < n就是有环。 - 多解：题目若要求字典序最小，用
PriorityQueue替代Queue。