什么是拓扑排序拓扑排序是对**有向无环图DAG, Directed Acyclic Graph**的节点进行线性排序使得对于图中的每一条有向边u → v节点u在排序中都位于节点v之前。核心特性仅适用于 DAG图必须无环否则无法进行拓扑排序结果不唯一一个 DAG 可能有多个合法的拓扑排序应用场景任务调度、课程选修计划、编译依赖、数据流处理等两种经典算法1. Kahn 算法BFS 思路核心思想不断移除入度为 0 的节点1. 计算所有节点的入度 2. 将所有入度为 0 的节点加入队列 3. 依次取出节点将其邻接节点入度减 1 4. 若邻接节点入度变为 0加入队列 5. 重复直到队列为空 6. 检查是否所有节点都被处理判断是否有环2. DFS 算法核心思想利用 DFS 的完成时间逆序1. 对图进行 DFS 遍历 2. 当某个节点的所有邻接节点都访问完成后将该节点加入结果 3. 最后将结果逆序即为拓扑排序Java 实现Kahn 算法importjava.util.*;publicclassTopologicalSort{// 邻接表表示图privateListListIntegergraph;privateintn;publicTopologicalSort(intn){this.nn;this.graphnewArrayList();for(inti0;in;i){graph.add(newArrayList());}}// 添加有向边 u - vpublicvoidaddEdge(intu,intv){graph.get(u).add(v);}// Kahn 算法BFSpublicListIntegerkahnSort(){// 1. 计算入度int[]inDegreenewint[n];for(intu0;un;u){for(intv:graph.get(u)){inDegree[v];}}// 2. 入度为0的节点入队QueueIntegerqueuenewLinkedList();for(inti0;in;i){if(inDegree[i]0){queue.offer(i);}}// 3. BFS 处理ListIntegerresultnewArrayList();while(!queue.isEmpty()){intuqueue.poll();result.add(u);for(intv:graph.get(u)){inDegree[v]--;if(inDegree[v]0){queue.offer(v);}}}// 4. 检查是否有环if(result.size()!n){thrownewRuntimeException(图中存在环无法进行拓扑排序);}returnresult;}// DFS 算法publicListIntegerdfsSort(){boolean[]visitednewboolean[n];boolean[]onPathnewboolean[n];// 用于检测环DequeIntegerstacknewArrayDeque();// 用栈存储结果for(inti0;in;i){if(!visited[i]){dfs(i,visited,onPath,stack);}}ListIntegerresultnewArrayList();while(!stack.isEmpty()){result.add(stack.pop());}returnresult;}privatevoiddfs(intu,boolean[]visited,boolean[]onPath,DequeIntegerstack){visited[u]true;onPath[u]true;for(intv:graph.get(u)){if(onPath[v]){thrownewRuntimeException(图中存在环);}if(!visited[v]){dfs(v,visited,onPath,stack);}}onPath[u]false;stack.push(u);// 后序遍历位置加入结果}// 测试publicstaticvoidmain(String[]args){// 示例课程选修 0-2, 1-2, 2-3, 2-4// 表示课程0和1是课程2的先修课课程2是课程3和4的先修课TopologicalSorttsnewTopologicalSort(5);ts.addEdge(0,2);ts.addEdge(1,2);ts.addEdge(2,3);ts.addEdge(2,4);System.out.println(Kahn算法结果: ts.kahnSort());System.out.println(DFS算法结果: ts.dfsSort());// 输出可能是: [0, 1, 2, 3, 4] 或 [1, 0, 2, 4, 3] 等合法排序}}图解示例0 1 入度表: 0:0, 1:0, 2:2, 3:1, 4:1 \ / ↘ ↘ 2 → 3 ↓ 4 Kahn算法执行过程 1. 初始入度为0: [0, 1]加入结果 2. 移除02的入度变为1移除12的入度变为0加入队列 3. 移除23和4的入度变为0加入队列 4. 依次移除3、4 拓扑排序结果: [0, 1, 2, 3, 4] 或 [1, 0, 2, 4, 3] 等复杂度分析算法时间复杂度空间复杂度Kahn (BFS)O(V E)O(V)DFSO(V E)O(V)其中 V 是顶点数E 是边数。实际应用Maven/Gradle 依赖解析确定 jar 包的加载顺序Makefile 编译顺序确定源文件的编译先后数据库迁移脚本按依赖关系执行 DDLSpark 任务调度确定 RDD 转换的执行顺序