JAVA:实现TopologicalSort拓扑排序算法（附带源码）
一、项目背景详细介绍
在有向无环图（DAG, Directed Acyclic Graph）中，**拓扑排序（Topological Sort）**用于线性化地表示各节点的先后依赖关系：若存在边 u→v，则在排序序列中 u 必须出现在 v 之前。拓扑排序广泛应用于：
-
任务调度：在构建系统、流水线或作业依赖场景中，按照依赖关系确定可并行或串行执行的顺序。
-
包管理与构建工具：如 Maven、Gradle 在构建模块或安装库时解决依赖先后顺序。
-
编译器与语言解析：在语法分析中，对依赖语句进行排序。
-
课程规划：根据先修课程关系，生成可行的选课顺序。
本文将系统地介绍 Java 中两种常见的拓扑排序算法：基于入度的 Kahn 算法（BFS）和基于深度优先搜索（DFS）的后序遍历法，并提供可复用的代码实现与优化思路。
二、项目需求详细介绍
-
功能需求
-
提供工具类
TopologicalSorter，包含两种静态方法：public static List<Integer> topoSortKahn(int n, List<List<Integer>> adj); public static List<Integer> topoSortDFS(int n, List<List<Integer>> adj);-
n：顶点数（编号0…n-1）； -
adj：邻接表表示的有向图； -
返回一个长度为
n的拓扑序列；若图中含环，则抛出IllegalArgumentException。
-
-
-
性能需求
-
时间复杂度：O(n + m)，其中 m 为边数；
-
空间复杂度：O(n + m) 辅助存储；
-
-
健壮性需求
-
对
adj==null或adj.size()!=n抛IllegalArgumentException； -
若检测到环（入度永不归零或 DFS 发现回边），抛
IllegalArgumentException；
-
-
可扩展性需求
-
支持自定义顶点类型（泛型）；
-
可输出所有可能的拓扑序（需额外回溯）；
-
提供并行版本或分布式实现思路；
-
-
代码规范
-
Java 8+；
-
方法内部无共享全局状态，线程安全；
-
代码注释清晰。
-
三、相关技术详细介绍
-
Kahn 算法（BFS）
-
维护每个节点的入度数组
inDeg[]； -
将所有入度为 0 的节点入队；
-
逐个出队，将其加入结果，并将其所有出边目标节点入度减 1；若新入度为 0 则入队；
-
最终若处理节点数不足
n，说明存在环。
-
-
DFS 后序法
-
访问每个未被标记的节点，进行递归 DFS；
-
在递归返回时将节点压入栈（或列表前端），确保所有子节点先入栈；
-
如果在 DFS 过程中发现“回到正在访问的节点”，则说明有环。
-
-
环检测
-
Kahn 算法通过最终结果长度与
n比较； -
DFS 维护三色标记（0=未访问，1=访问中，2=已访问）检测回边。
-
-
邻接表表示
-
使用
List<List<Integer>>或List<Integer>[]存储边列表。
-
四、实现思路详细介绍
4.1 Kahn 算法
-
初始化：
-
创建
int[] inDeg = new int[n]，遍历adj累加目标节点入度； -
Deque<Integer> queue收集所有inDeg[i]==0节点；
-
-
处理队列：
while queue 非空:
u = queue.remove() result.add(u)
for v in adj.get(u): if (--inDeg[v] == 0) queue.add(v) -
环检测：
-
若
result.size() < n，抛异常。
-
4.2 DFS 后序法
-
三色标记：
int[] state（0、1、2）； -
递归函数
dfs(u)：-
标记
state[u]=1（访问中）； -
对每个
vinadj.get(u)：-
若
state[v]==1，检测到环； -
若
state[v]==0，dfs(v)；
-
-
标记
state[u]=2并result.add(u)；
-
-
遍历所有节点：
-
对每个
u=0…n-1未访问的调用dfs(u)； -
最后将
result反转得到拓扑序。
-
五、完整实现代码
// ===== 文件：TopologicalSorter.java =====
package com.example.graph;
import java.util.*;
/**
* TopologicalSorter 工具类：提供两种拓扑排序实现
*/
public class TopologicalSorter {
/**
* 方法一：Kahn 算法（BFS）
* @param n 节点数，编号 0..n-1
* @param adj 邻接表表示的有向图
* @return 拓扑排序列表
* @throws IllegalArgumentException 若输入非法或图中含环
*/
public static List<Integer> topoSortKahn(int n, List<List<Integer>> adj) {
if (adj == null || adj.size() != n) {
throw new IllegalArgumentException("邻接表非法");
}
int[] inDeg = new int[n];
for (List<Integer> nbrs : adj) {
for (int v : nbrs) {
if (v < 0 || v >= n) throw new IllegalArgumentException("边终点越界");
inDeg[v]++;
}
}
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (inDeg[i] == 0) queue.add(i);
}
List<Integer> result = new ArrayList<>(n);
while (!queue.isEmpty()) {
int u = queue.remove();
result.add(u);
for (int v : adj.get(u)) {
if (--inDeg[v] == 0) queue.add(v);
}
}
if (result.size() < n) {
throw new IllegalArgumentException("图中包含环，无法拓扑排序");
}
return result;
}
/**
* 方法二：DFS 后序遍历法
* @param n 节点数
* @param adj 邻接表
* @return 拓扑排序列表
* @throws IllegalArgumentException 若输入非法或图中含环
*/
public static List<Integer> topoSortDFS(int n, List<List<Integer>> adj) {
if (adj == null || adj.size() != n) {
throw new IllegalArgumentException("邻接表非法");
}
int[] state = new int[n]; // 0=unseen,1=visiting,2=visited
List<Integer> result = new ArrayList<>(n);
for (int u = 0; u < n; u++) {
if (state[u] == 0) {
dfs(u, adj, state, result);
}
}
Collections.reverse(result);
return result;
}
private static void dfs(int u, List<List<Integer>> adj,
int[] state, List<Integer> result) {
state[u] = 1; // visiting
for (int v : adj.get(u)) {
if (v < 0 || v >= state.length) {
throw new IllegalArgumentException("边终点越界");
}
if (state[v] == 1) {
throw new IllegalArgumentException("图中包含环，无法拓扑排序");
}
if (state[v] == 0) {
dfs(v, adj, state, result);
}
}
state[u] = 2; // visited
result.add(u);
}
}
// ===== 文件：Main.java =====
package com.example.graph;
import java.util.*;
public class Main {
public static void main(String[] args) {
// 示例图：0→1→2, 0→2, 3→1
int n = 4;
List<List<Integer>> adj = Arrays.asList(
Arrays.asList(1, 2), // 0 的邻居
Collections.singletonList(2), // 1→2
Collections.emptyList(), // 2→
Collections.singletonList(1) // 3→1
);
System.out.println("Kahn 算法拓扑序: " + TopologicalSorter.topoSortKahn(n, adj));
System.out.println("DFS 算法拓扑序: " + TopologicalSorter.topoSortDFS(n, adj));
// 构造含环图测试
adj = Arrays.asList(
Collections.singletonList(1),
Collections.singletonList(2),
Collections.singletonList(0)
);
try {
TopologicalSorter.topoSortKahn(3, adj);
} catch (IllegalArgumentException ex) {
System.out.println("Kahn 检测环: " + ex.getMessage());
}
}
}
六、代码详细解读
-
topoSortKahn-
计算每个节点的入度；
-
初始化队列，依次出队入度为 0 的节点，更新其后继节点入度；
-
若最终结果长度小于
n，则检测到环。
-
-
topoSortDFS-
维护三色标记数组
state[]，递归 DFS； -
“访问中”节点再被触及即为回边，检测到环；
-
后序添加节点至
result，最后反转得到拓扑序。
-
七、项目详细总结
-
两种算法对比
-
Kahn（BFS）：直观、易于环检测；
-
DFS 后序：代码简洁、复用 DFS 框架；
-
-
复杂度
-
时间 O(n + m)，空间 O(n + m)；
-
-
环检测
-
Kahn 通过入度清零数量；DFS 通过三色标记。
-
八、项目常见问题及解答
-
为何需要环检测？
拓扑排序仅对 DAG 有意义，有环时不存在任何线性化序列。 -
能否返回所有拓扑序？
需在 Kahn 算法中回溯所有分支，复杂度高，仅适合小规模图。 -
如何支持泛型顶点？
将int替换为T，使用Map<T,List<T>>存图并对Queue<T>/List<T>操作。 -
并行拓扑排序？
可并行移除所有当前入度为 0 的节点并更新后继，但需同步入度数组； -
图表示方式多样性？
可使用邻接矩阵或边列表，根据图稠密度选择最优结构。
九、扩展方向与性能优化
-
支持海量图
-
使用外部存储（如数据库或大数据平台）分布式计算入度并行移除。
-
-
增量更新
-
在动态图中维护增量拓扑序，插入/删除边时局部调整。
-
-
流式输出
-
将拓扑序以流式方式输出到下游系统，边生成边消费；
-
-
可视化
-
在 GUI 中动态展示节点移出顺序与依赖关系变化；
-
-
自平衡负载
-
在并行执行时按节点度或层级划分任务，减少线程竞争。
-
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
21
0- 0
已为社区贡献484条内容
所有评论(0)