一、什么是拓扑排序？

二、拓扑排序的算法实现

1 BFS算法实现

（1）算法思路

（2）代码实现（Java）

2 DFS算法实现

（1）算法思路

（2）代码实现（Java）

三、实战用例：具有优先级的任务调度系统

1 问题描述

2 解决方案

3 Java 实现

一、什么是拓扑排序？

拓扑排序（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]; // 记录是否存在环
// 初始化所有节点为 UNVISITEDfor (String node : graph.keySet()) {stateMap.put(node, State.UNVISITED);for (String neighbor : graph.get(node)) {stateMap.putIfAbsent(neighbor, State.UNVISITED);}}
// 对每个节点进行 DFSfor (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;}@Overridepublic 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 和 t1t3.setInDegree(1); // 来自 t2List<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 + " ");}}
}

测试结果