圖論(2)算法之拓撲排序介紹

一、什么是拓撲排序？

二、拓撲排序的算法實現

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 + " ");}}
}

測試結果