当前位置：首页 > news >正文

拓扑排序（Topological Sort）

news 2026/8/27 17:01:59

什么是拓扑排序

拓扑排序是对**有向无环图（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{// 邻接表表示图privateList<List<Integer>>graph;privateintn;publicTopologicalSort(intn){this.n=n;this.graph=newArrayList<>();for(inti=0;i<n;i++){graph.add(newArrayList<>());}}// 添加有向边 u -> vpublicvoidaddEdge(intu,intv){graph.get(u).add(v);}// Kahn 算法（BFS）publicList<Integer>kahnSort(){// 1. 计算入度int[]inDegree=newint[n];for(intu=0;u<n;u++){for(intv:graph.get(u)){inDegree[v]++;}}// 2. 入度为0的节点入队Queue<Integer>queue=newLinkedList<>();for(inti=0;i<n;i++){if(inDegree[i]==0){queue.offer(i);}}// 3. BFS 处理List<Integer>result=newArrayList<>();while(!queue.isEmpty()){intu=queue.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 算法publicList<Integer>dfsSort(){boolean[]visited=newboolean[n];boolean[]onPath=newboolean[n];// 用于检测环Deque<Integer>stack=newArrayDeque<>();// 用栈存储结果for(inti=0;i<n;i++){if(!visited[i]){dfs(i,visited,onPath,stack);}}List<Integer>result=newArrayList<>();while(!stack.isEmpty()){result.add(stack.pop());}returnresult;}privatevoiddfs(intu,boolean[]visited,boolean[]onPath,Deque<Integer>stack){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的先修课TopologicalSortts=newTopologicalSort(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. 移除0，2的入度变为1；移除1，2的入度变为0，加入队列 3. 移除2，3和4的入度变为0，加入队列 4. 依次移除3、4 拓扑排序结果: [0, 1, 2, 3, 4] 或 [1, 0, 2, 4, 3] 等