数据结构与算法 / 系统课时
拓扑排序
拓扑排序
拓扑排序把有向依赖关系转换为满足先后约束的线性序列。本课将用入度法与深度优先搜索处理同一张图,并通过已处理顶点数或 DFS 颜色状态检测依赖环。
学习目标
- 判断一张有向图是否具备拓扑序列。
- 使用 Kahn 入度法和 DFS 生成合法拓扑序列。
- 理解两种方法检测环的条件与复杂度。
问题定义与适用条件
设有向边 u -> v 表示任务 u 必须先于任务 v 完成。拓扑排序要找到一个顶点序列,使每条边的起点都出现在终点之前。只有有向无环图,也就是 DAG,才存在拓扑序列;同一张 DAG 可能有多个正确答案。
课程依赖、构建任务、数据库迁移和工作流编排都可抽象成这一问题。若图中存在依赖环,例如 B -> C -> E -> F -> B,任何顶点都无法成为完整线性顺序中的合法起点,因此必须报告失败,而不是返回部分结果。
两种核心方法
Kahn 入度法先统计每个顶点的入度,把所有入度为 0 的顶点放入队列。每取出一个顶点,就删除它发出的边,并把新变为 0 的顶点加入队列。最终处理数等于顶点数时得到拓扑序列,否则图中存在环。
DFS 方法使用白、灰、黑三种状态:白色表示未访问,灰色表示正在当前递归路径中,黑色表示已经完成。顶点完成时压入栈,最终按栈顺序得到拓扑序列;搜索到灰色顶点说明出现回边,可立即判定存在环。
| 方法 | 主要结构 | 生成顺序的时机 | 环检测条件 |
|---|---|---|---|
| Kahn 入度法 | 入度数组与零入度队列 | 顶点出队时加入结果 | 处理顶点数小于总顶点数 |
| DFS | 三色状态与栈 | 顶点完成时压栈 | 遇到指向灰色顶点的边 |
执行过程
下图把零入度队列的变化、DFS 完成顺序和环检测放在同一张依赖图中。阅读时重点观察:入度法不断移除前置约束,DFS 则沿路径深入,并在回溯阶段确定顺序。

完整可运行示例
下面的 Java 17 程序对同一张 DAG 分别执行两种算法,并向副本加入 F -> B,验证 DFS 能识别依赖环。优先队列用于稳定选择字母较小的零入度顶点,因此入度法输出可重复。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.PriorityQueue;
public class TopologicalSortDemo {
public static void main(String[] args) {
List<List<Integer>> graph = createGraph(6);
addEdge(graph, 0, 2); // A -> C
addEdge(graph, 1, 2); // B -> C
addEdge(graph, 1, 3); // B -> D
addEdge(graph, 2, 4); // C -> E
addEdge(graph, 3, 5); // D -> F
addEdge(graph, 4, 5); // E -> F
System.out.println("入度法拓扑序列: " + format(kahnSort(graph)));
System.out.println("DFS 拓扑序列: " + format(dfsTopologicalSort(graph)));
List<List<Integer>> cyclicGraph = copyGraph(graph);
addEdge(cyclicGraph, 5, 1); // F -> B,形成依赖环
System.out.println("有环图 DFS 检测: " + hasCycle(cyclicGraph));
}
private static List<Integer> kahnSort(List<List<Integer>> graph) {
int[] indegree = new int[graph.size()];
for (List<Integer> edges : graph) {
for (int to : edges) {
indegree[to]++;
}
}
PriorityQueue<Integer> ready = new PriorityQueue<>();
for (int vertex = 0; vertex < indegree.length; vertex++) {
if (indegree[vertex] == 0) {
ready.offer(vertex);
}
}
List<Integer> order = new ArrayList<>();
while (!ready.isEmpty()) {
int current = ready.poll();
order.add(current);
for (int next : graph.get(current)) {
if (--indegree[next] == 0) {
ready.offer(next);
}
}
}
if (order.size() != graph.size()) {
throw new IllegalStateException("图中存在环,无法生成拓扑序列");
}
return order;
}
private static List<Integer> dfsTopologicalSort(List<List<Integer>> graph) {
int[] color = new int[graph.size()];
Deque<Integer> stack = new ArrayDeque<>();
for (int vertex = 0; vertex < graph.size(); vertex++) {
if (color[vertex] == 0 && !dfs(vertex, graph, color, stack)) {
throw new IllegalStateException("图中存在环,无法生成拓扑序列");
}
}
return new ArrayList<>(stack);
}
private static boolean dfs(
int current,
List<List<Integer>> graph,
int[] color,
Deque<Integer> stack) {
color[current] = 1;
for (int next : graph.get(current)) {
if (color[next] == 1) {
return false;
}
if (color[next] == 0 && !dfs(next, graph, color, stack)) {
return false;
}
}
color[current] = 2;
stack.push(current);
return true;
}
private static boolean hasCycle(List<List<Integer>> graph) {
int[] color = new int[graph.size()];
for (int vertex = 0; vertex < graph.size(); vertex++) {
if (color[vertex] == 0 && !dfs(vertex, graph, color, new ArrayDeque<>())) {
return true;
}
}
return false;
}
private static List<List<Integer>> createGraph(int size) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < size; i++) {
graph.add(new ArrayList<>());
}
return graph;
}
private static List<List<Integer>> copyGraph(List<List<Integer>> graph) {
List<List<Integer>> copy = createGraph(graph.size());
for (int i = 0; i < graph.size(); i++) {
copy.get(i).addAll(graph.get(i));
}
return copy;
}
private static void addEdge(List<List<Integer>> graph, int from, int to) {
graph.get(from).add(to);
}
private static String format(List<Integer> order) {
List<String> labels = new ArrayList<>();
for (int vertex : order) {
labels.add(String.valueOf((char) ('A' + vertex)));
}
return String.join(" -> ", labels);
}
}将代码保存为 TopologicalSortDemo.java,然后运行:
javac TopologicalSortDemo.java
java TopologicalSortDemo预期输出
入度法拓扑序列: A -> B -> C -> D -> E -> F
DFS 拓扑序列: B -> D -> A -> C -> E -> F
有环图 DFS 检测: true两条拓扑序列不同但都满足全部边的先后约束,这正说明拓扑序列通常不唯一。
复杂度、Tips 与常见错误
两种方法都会访问每个顶点和每条边一次,时间复杂度为 。使用邻接表时,图、入度数组、颜色数组、队列或栈合计占用 空间;递归 DFS 还需考虑最坏 的调用栈深度。
- 需要稳定且可重复的输出时,可用优先队列选择当前编号最小的零入度顶点。
- Kahn 算法必须在图副本上修改入度,避免污染后续计算使用的原始数据。
- DFS 不能只用布尔
visited检测环;必须区分“正在访问”和“已经完成”,否则无法识别回边。 - 结果少于全部顶点时不得把部分序列当成成功输出,这通常意味着图中存在环。
本课练习
- 把示例中的优先队列改为普通队列,记录输出是否变化,并逐条验证所有有向边仍满足先后关系。
- 为 Kahn 方法增加环检测演示:向原图加入
F -> B,捕获异常并输出固定错误信息。 - 编写验证函数,接收图与候选序列,检查每条边的起点位置是否小于终点位置;合法序列返回
true。
本课总结
- 拓扑排序只适用于 DAG,结果可能不唯一,但必须满足每条有向边的先后约束。
- Kahn 方法通过零入度顶点推进,DFS 方法通过完成时间逆序构造结果。
- 处理数不足或遇到指向灰色顶点的回边,都表示图中存在依赖环。
下一课预告
下一课将学习“强连通分量”,把有向图中能够互相到达的顶点归为同一组,并用两次 DFS 找出这些循环依赖区域。