目录
一、什么是拓扑排序？
拓扑排序（Topological Sorting）是图论中的一种排序方式，主要用于有向无环图（DAG, Directed Acyclic Graph）。
在拓扑排序中，如果图中的边 u → v 表示任务 u 必须在任务 v 之前完成，那么拓扑排序就返回一个任务执行顺序，使得所有的先决任务都排在其后续任务之前。
如果图中存在环（即不是DAG），就不存在合法的拓扑排序。
二、拓扑排序的算法实现
我们以无权图（不含权重）为例，使用 Java 实现拓扑排序的两种主流算法：
1 BFS算法实现
Kahn算法是一种经典的基于BFS（广度优先搜索）的拓扑排序算法。
（1）算法思路
统计每个节点的入度（被依赖的次数）。
将所有入度为 0 的节点加入队列。
从队列中取出一个节点，将其加入拓扑排序结果。
遍历该节点的所有邻接节点，将邻接节点的入度减 1；若入度变为 0，则加入队列。
重复步骤 3 和 4，直到队列为空。
如果结果中的节点数不等于图的节点总数，则说明图中存在环。
（2） 代码实现（Java）
import java.util.*;
public class TopSort {
public static List<String> topSortKahn(Map<String, List<String>> graph) {
// 1. 计算每个节点的入度
Map<String, Integer> indegree = new HashMap<>();
for (String u : graph.keySet()) {
// 确保所有节点都在 indegree 中
indegree.putIfAbsent(u, 0);
for (String v : graph.get(u)) {
indegree.put(v, indegree.getOrDefault(v, 0) + 1);
}
}
// 2. 所有入度为 0 的节点入队
Queue<String> queue = new LinkedList<>();
for (Map.Entry<String, Integer> entry : indegree.entrySet()) {
if (entry.getValue() == 0) {
queue.offer(entry.getKey());
}
}
// 3. 进行拓扑排序
List<String> result = new ArrayList<>();
while (!queue.isEmpty()) {
String node = queue.poll();
result.add(node);
List<String> neighbors = graph.getOrDefault(node, new ArrayList<>());
for (String neighbor : neighbors) {
indegree.put(neighbor, indegree.get(neighbor) - 1);
if (indegree.get(neighbor) == 0) {
queue.offer(neighbor);
}
}
}
// 4. 如果排序结果数量 < 节点总数，说明有环
if (result.size() != indegree.size()) {
return null;
}
return result;
}
// 测试用例
public static void main(String[] args) {
Map<String, List<String>> graph1 = new HashMap<>();
graph1.put("A", Arrays.asList("C"));
graph1.put("B", Arrays.asList("C", "D"));
graph1.put("C", Arrays.asList("E"));
graph1.put("D", Arrays.asList("F"));
graph1.put("E", Arrays.asList("H", "F"));
graph1.put("F", Arrays.asList("G"));
graph1.put("G", Collections.emptyList());
graph1.put("H", Collections.emptyList());
System.out.println("拓扑排序结果: " + topSortKahn(graph1));
// 带有环的图
Map<String, List<String>> graph2 = new HashMap<>();
graph2.put("A", Arrays.asList("C"));
graph2.put("B", Arrays.asList("C", "D"));
graph2.put("C", Arrays.asList("E"));
graph2.put("D", Arrays.asList("F"));
graph2.put("E", Arrays.asList("C")); // 构成了环
graph2.put("F", Arrays.asList("G"));
graph2.put("G", Collections.emptyList());
System.out.println("拓扑排序结果（存在环）: " + topSortKahn(graph2));
}
}
测试结果:
拓扑排序结果: [A, B, C, D, E, H, F, G] 拓扑排序结果（存在环）: null
2 DFS算法实现
（1）算法思路
使用 DFS 遍历图。
遍历过程中，将当前节点标记为“正在访问”状态。
递归访问邻接节点，如果发现邻接节点已经在访问中，说明存在环。
所有邻接节点访问完后，将当前节点加入结果栈，并标记为“访问完成”。
最终将栈反转，得到拓扑排序结果。
（2） 代码实现（Java）
import java.util.*;
public class TopSort {
// 枚举节点访问状态
enum State { UNVISITED, VISITING, VISITED }
public static List<String> topSortDfs(Map<String, List<String>> graph) {
Map<String, State> stateMap = new HashMap<>();
List<String> result = new ArrayList<>();
boolean[] hasCycle = new boolean[1]; // 记录是否存在环
// 初始化所有节点为 UNVISITED
for (String node : graph.keySet()) {
stateMap.put(node, State.UNVISITED);
for (String neighbor : graph.get(node)) {
stateMap.putIfAbsent(neighbor, State.UNVISITED);
}
}
// 对每个节点进行 DFS
for (String node : stateMap.keySet()) {
if (stateMap.get(node) == State.UNVISITED) {
dfs(node, graph, stateMap, result, hasCycle);
if (hasCycle[0]) {
return null; // 有环
}
}
}
// 逆序输出拓扑排序结果
Collections.reverse(result);
return result;
}
private static void dfs(String node, Map<String, List<String>> graph, Map<String, State> stateMap, List<String> result, boolean[] hasCycle) {
stateMap.put(node, State.VISITING);
for (String neighbor : graph.getOrDefault(node, Collections.emptyList())) {
State neighborState = stateMap.get(neighbor);
if (neighborState == State.UNVISITED) {
dfs(neighbor, graph, stateMap, result, hasCycle);
if (hasCycle[0]) return;
} else if (neighborState == State.VISITING) {
hasCycle[0] = true; // 检测到环
return;
}
}
stateMap.put(node, State.VISITED);
result.add(node); // 后序加入
}
// 测试用例
public static void main(String[] args) {
Map<String, List<String>> graph1 = new HashMap<>();
graph1.put("A", Arrays.asList("C"));
graph1.put("B", Arrays.asList("C", "D"));
graph1.put("C", Arrays.asList("E"));
graph1.put("D", Arrays.asList("F"));
graph1.put("E", Arrays.asList("H", "F"));
graph1.put("F", Arrays.asList("G"));
graph1.put("G", Collections.emptyList());
graph1.put("H", Collections.emptyList());
System.out.println("拓扑排序结果: " + topSortDfs(graph1));
// 带有环的图
Map<String, List<String>> graph2 = new HashMap<>();
graph2.put("A", Arrays.asList("C"));
graph2.put("B", Arrays.asList("C", "D"));
graph2.put("C", Arrays.asList("E"));
graph2.put("D", Arrays.asList("F"));
graph2.put("E", Arrays.asList("C")); // 构成了环
graph2.put("F", Arrays.asList("G"));
graph2.put("G", Collections.emptyList());
System.out.println("拓扑排序结果（存在环）: " + topSortDfs(graph2));
}
}
测试结果:
拓扑排序结果: [B, D, A, C, E, F, G, H] 拓扑排序结果（存在环）: null
三、实战用例：具有优先级的任务调度系统
1 问题描述
我们有一个调度系统，其每个任务可能依赖其他任务，并且每个任务有一个优先级值（值越大优先级越高）。系统要求先执行优先级高的任务，同时也要保证所有依赖任务已经执行。
2 解决方案
我们结合拓扑排序 + 优先级排序解决：
将任务依赖建图。
使用拓扑排序（Kahn 算法）。
使用优先级高的任务优先执行：将普通队列替换成优先级队列，先处理高优先级入度为 0 的任务。
3 Java 实现
import java.util.*;
public class TaskSchedulerWithPriority {
public static class Task {
private int id;
private int priority;
private List<Task> edges = new ArrayList<>(); // 边列表
private int inDegree = 0; // 入度
public Task(int id, int priority) {
this.id = id;
this.priority = priority;
}
public int getId() {
return id;
}
public int getPriority() {
return priority;
}
public void setPriority(int priority) {
this.priority = priority;
}
public List<Task> getEdges() {
return edges;
}
public int getInDegree() {
return inDegree;
}
public void setInDegree(int inDegree) {
this.inDegree = inDegree;
}
@Override
public String toString() {
return "Task{id=" + id + ", priority=" + priority + "}";
}
}
/**
* 按优先级和依赖顺序进行拓扑排序
*/
public static List<Task> scheduleTasks(List<Task> tasks) {
// 大顶堆：优先处理优先级高的任务
PriorityQueue<Task> queue = new PriorityQueue<>(
(a, b) -> b.getPriority() - a.getPriority()
);
// 初始化：将所有入度为 0 的任务放入队列
for (Task task : tasks) {
if (task.getInDegree() == 0) {
queue.offer(task);
}
}
List<Task> result = new ArrayList<>();
while (!queue.isEmpty()) {
Task current = queue.poll();
result.add(current);
// 遍历后继节点
for (Task neighbor : current.getEdges()) {
neighbor.setInDegree(neighbor.getInDegree()-1);
if (neighbor.getInDegree() == 0) {
queue.offer(neighbor);
}
}
}
// 检查是否有环
if (result.size() != tasks.size()) {
throw new RuntimeException("存在循环依赖，无法完成调度");
}
return result;
}
public static void main(String[] args) {
// 创建任务
Task t0 = new Task(0, 10);
Task t1 = new Task(1, 20);
Task t2 = new Task(2, 10);
Task t3 = new Task(3, 20);
// 构建依赖关系 (邻接表 + 入度)
t0.getEdges().add(t2);
t1.getEdges().add(t2);
t2.getEdges().add(t3);
t2.setInDegree(2); // 来自 t0 和 t1
t3.setInDegree(1); // 来自 t2
List<Task> tasks = Arrays.asList(t0, t1, t2, t3);
// 调度
List<Task> schedule = scheduleTasks(tasks);
System.out.print("调度任务执行顺序: ");
for (Task task : schedule) {
System.out.print(task.id + " ");
}
}
}
测试结果
调度任务执行顺序: [1, 0, 2, 3]
表示优先级高的任务 1 和 0 会先执行，然后是它们的依赖任务 2 和最终任务 3。