外观
18 - 拓扑排序:任务依赖如何安排出合法执行顺序
前置阅读:17 - 图的 DFS 与 BFS。
摘要
假设发布前必须先构建,构建前必须先生成代码,怎样安排任务才不会提前执行依赖尚未完成的步骤?拓扑排序把这些先后约束整理成一个合法顺序;如果任务相互等待,算法也能发现循环依赖。
本文先建立依赖图模型,再实现 Kahn 算法,解释顺序不唯一和环检测的含义,最后讨论它与真实任务调度的区别。
1. 模型
把每个任务表示为一个节点。若任务 B 依赖 A,就建立有向边 A -> B,表示 A 必须在 B 之前完成。例如,“生成代码 → 构建 → 发布”是一条依赖链。这里的箭头从前置任务指向后续任务,不能按“B 依赖 A”的文字顺序建成 B -> A。
拓扑序是包含全部节点、且每个节点恰好出现一次的序列。对每条边 A -> B,序列中 A 都必须排在 B 前面。它只规定必须遵守的先后关系,不要求本来互不依赖的任务也按固定顺序排列。
沿有向边出发又回到原节点,就形成了有向环。若有 A -> B -> C -> A,A 必须先于 B,B 必须先于 C,C 又必须先于 A,无法同时满足。因此,只有 **DAG(Directed Acyclic Graph,有向无环图)**存在拓扑序;没有环时,可以不断取出没有剩余前置依赖的节点,直到处理完全部节点。
下文用 V 表示节点数、E 表示边数。节点编号为 0 到 n - 1;入度是指向某节点的边数,例如 0 -> 2、1 -> 2 使节点 2 的初始入度为 2。
2. Kahn 算法
Kahn 算法用入度记录“还有多少条前置约束尚未解除”。入度为 0 的节点可以作为下一个节点,因为它已经不需要等待其他未处理节点。
- 建立邻接表,为每个节点保存它指向的后续节点,并统计初始入度。
- 把所有入度为 0 的节点加入队列,包括没有任何边的孤立节点。
- 取出一个节点并追加到结果中,遍历它的出边,将每个后续节点的入度减 1。
- 某个后续节点的入度降到 0 时,将其入队;重复处理,直到队列为空。
- 若结果包含全部节点,返回拓扑序;否则报告存在环。
这里的“删除出边”是逻辑上的移除:代码保留邻接表,只递减入度。取出节点表示把它放进离线计算的顺序,并没有执行真实任务。
下面是方法片段,需要放入类中,并导入 java.util 中的 List、ArrayList。输入要求 n >= 0,edges 非空引用,每条边包含两个合法节点编号;代码没有额外参数校验。
java
static List<Integer> topologicalSort(int n, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
int[] indegree = new int[n];
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
indegree[edge[1]]++;
}
var queue = new java.util.ArrayDeque<Integer>();
for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.offer(i);
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
int node = queue.poll();
order.add(node);
for (int next : graph.get(node)) {
if (--indegree[next] == 0) queue.offer(next);
}
}
if (order.size() != n) throw new IllegalStateException("dependency cycle");
return order;
}每次取出的节点都没有剩余前置依赖,因此把它追加到结果不会违反任何边的先后约束。解除它的出边后,后续节点只有在全部前置约束解除时才会入队。这就是算法持续生成合法顺序的原因。
普通队列版中,每个节点最多入队、出队一次,每条边只在起点出队时处理一次,时间复杂度为 O(V+E)。邻接表、入度数组、队列和结果列表合计占 O(V+E) 空间;不计邻接表时,辅助空间为 O(V)。这些是代码分析,不是性能测量。
3. 顺序为什么不唯一
在无环图中,某一步可能有多个入度为 0 的节点。它们之间没有尚未满足的依赖关系,所以先选哪一个都可以。例如 0 -> 2、1 -> 2 既允许 [0, 1, 2],也允许 [1, 0, 2]。
若业务要求字典序最小,即从左到右比较两个序列时,让第一个不同位置的编号尽量小,可以使用优先队列替代普通队列,每次取出当前可选节点中编号最小的一个。普通队列在固定输入及遍历顺序下也能得到确定结果,但不保证字典序最小。
4. 环检测结果如何解释
队列为空但仍有节点未处理,说明剩余节点都还有前置约束。任选一个剩余节点,不断追溯它的剩余前置节点;节点数有限,最终必然遇到重复节点,因此剩余部分存在环。
但未处理节点不一定都在环上。例如 A -> B -> A,另有 B -> C,C 不属于环,却也会被环阻塞。返回未归零的节点集合可以缩小排查范围,不能直接把这个集合称为环路。
如果排障需要具体依赖链,可以对剩余子图执行三色 DFS:将节点区分为未访问、当前递归路径中、已经完成。发现指向当前递归路径中节点的边时,就找到了闭合的环;沿 DFS 的父指针(记录从哪个节点进入当前节点)恢复路径,再补上这条边,可得到 A -> B -> C -> A 这样的环路。只保存普通访问标记或无条件记录前驱,不足以完成这一步。下面的排序代码只报告存在环,没有实现环路恢复。
5. 完整可运行示例:排序与环检测
下面的完整类对应文件名 TopologicalSortDemo.java,只使用 Java 标准集合,无外部依赖。它沿用第 2 节的输入条件,但改用优先队列,每次选择最小编号的就绪节点。n = 0 且无边时返回空列表。
第 2 节片段使用局部变量 var,按语法要求需要 Java 10 或更高版本;下面的完整类没有使用 var。
java
import java.util.*;
/**
* 可运行示例:拓扑排序:任务依赖如何安排出合法执行顺序。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class TopologicalSortDemo {
static List<Integer> sort(int n, int[][] edges) {
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
int[] in = new int[n];
for (int[] e : edges) {
// u -> v 表示 v 依赖 u,因此增加 v 的未完成前置数量。
g.get(e[0]).add(e[1]);
in[e[1]]++;
}
PriorityQueue<Integer> ready = new PriorityQueue<>();
for (int i = 0; i < n; i++) if (in[i] == 0) ready.offer(i);
List<Integer> out = new ArrayList<>();
while (!ready.isEmpty()) {
// 队列中只包含所有前置节点均已排入结果的节点。
int u = ready.poll();
out.add(u);
for (int v : g.get(u)) if (--in[v] == 0) ready.offer(v);
}
// 无法处理全部节点,说明剩余子图不存在入度为 0 的入口,即存在环。
if (out.size() != n) throw new IllegalStateException("cycle detected");
return out;
}
// 运行入口:演示一个无环图和一个双节点环。
public static void main(String[] args) {
System.out.println(
sort(6, new int[][] { { 0, 2 }, { 1, 2 }, { 2, 3 }, { 2, 4 }, { 4, 5 } })
);
try {
sort(2, new int[][] { { 0, 1 }, { 1, 0 } });
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}手工推演
完整示例的初始零入度节点是 0、1。先取出 0,节点 2 的入度从 2 降到 1;再取出 1,节点 2 的入度降到 0,才能入队。取出 2 后,3、4 同时就绪;优先队列先取出 3,再取出 4,最后由 4 解除节点 5 的依赖。
因此,两行预期输出分别为 [0, 1, 2, 3, 4, 5] 和 cycle detected。这是手工推演,并非实测。第二次调用中,0、1 的入度都为 1,初始队列为空,结果节点数小于 2,因此抛出异常并由 main 打印异常消息。
对较小的依赖图 0→2、1→2、2→3,若增加 3→1,处理 0 后仍有 1→2→3→1 相互等待,环中的节点始终无法入队。
优先队列版仍然只扫描每条边一次,但每个节点的入队、出队操作最坏需要 O(log V) 时间,所以对 V >= 2,总时间为 O(E + V log V),总空间仍为 O(V+E)。优先队列用于选择最小编号,不是拓扑排序正确性的必要条件。
6. 工程应用
任务编排是在依赖约束之上安排任务启动、跟踪执行结果并处理失败。离线拓扑排序只计算一个合法顺序;实际调度器还要考虑并行执行、失败重试和资源限制。
假设依赖的含义是“前置任务成功后才能启动后续任务”,调度器必须等前置任务成功完成,才能递减后续任务的未完成依赖数。不能照搬排序代码,在任务刚出队或刚启动时就递减,否则后续任务可能在前置任务尚未完成时启动。多个任务依赖已满足、彼此无先后约束且资源允许时,可以并行执行。
调度器还必须区分两个状态:
- 拓扑就绪:所有依赖已经成功完成;
- 资源就绪:线程、连接、配额和下游容量允许启动。
节点失败后是阻断后继、跳过、补偿还是重试,属于工作流状态机,也就是任务有哪些状态、哪些事件允许它改变状态的规则。补偿是对已产生的业务效果执行约定的撤销或修复操作,这些策略不属于拓扑排序本身。
重试任务若会写数据、扣款或调用外部接口,还需要保证幂等性,即重复处理同一业务操作不会额外产生业务效果。并发完成回调和重复通知也必须避免让同一次成功重复递减依赖计数,否则可能过早释放后续任务。
7. 验证与排障
- 检查返回序列是否包含全部节点、每个节点是否恰好出现一次,再对输入中的每条边
u -> v检查 u 的位置是否早于 v; - 多个合法顺序时优先验证依赖约束;只有接口约定了选取规则,例如最小编号优先,才要求固定输出;
- 覆盖空图、无边图、单链、多个合法顺序、重复边、自环和多节点环;
- 重复边可以先去重,也可以按多条边计数,但建图、入度增加和后续递减必须一致。本文两份实现保留重复边,每份邻接记录都对应一次增加和一次递减,不会因此误报环;
- 本文代码的环路测试应验证会抛出异常;若另外实现了环路恢复,再检查输出链是否闭合、每条边是否确实存在;
- 调度停滞时区分依赖未满足、资源不足、任务失败和状态未持久化。
8. 容易踩的坑
- 边方向建反,输出变成与业务要求相反的先后顺序。
- 重复边只在一侧去重,使入度统计与邻接表递减不一致。
- 把递减后的入度数组当作初始状态复用;本文每次调用都会新建数组,复用图时也应重新统计或复制初始入度。
- 把一种拓扑序当作唯一结果,或把离线排序中的出队当作真实任务已完成。
- 仅凭未处理节点集合认定具体环路,无法区分环内节点与被环阻塞的后续节点。
9. 总结
拓扑排序通过不断移除无前置依赖的节点,生成合法顺序并暴露依赖环。
- 只有 DAG 才存在拓扑序。
- 无环图中出现多个可选零入度节点,意味着存在多个合法拓扑序。
- 工程调度还需在拓扑约束之上处理并发、资源和失败。