算法學習筆記：29.拓撲排序——從原理到實戰，涵蓋 LeetCode 與考研 408 例題

拓撲排序（Topological Sorting）是一種針對有向無環圖（DAG）的線性排序算法，它將圖中的頂點按照一定規則排列，使得對于圖中的任意一條有向邊 u→v，頂點 u 都排在頂點 v 之前。拓撲排序在任務調度、課程安排、編譯依賴等場景中有著廣泛應用。

拓撲排序的基本概念與適用場景

核心定義

有向無環圖（DAG）：頂點間的邊有方向，且不存在環路的圖。拓撲排序僅適用于 DAG，若圖中存在環，則不存在拓撲排序。

拓撲序：對于 DAG 中的頂點，存在一個線性序列 v?, v?, ..., v?，使得所有有向邊 v?→v? 均滿足 i < j。一個 DAG 可能存在多個拓撲序。

應用場景

任務調度：若任務 B 依賴任務 A，則 A 必須在 B 之前執行，拓撲排序可確定任務執行順序。

課程安排：大學課程存在先修關系（如 “數據結構” 需先修 “C 語言”），拓撲排序可生成合理的選課順序。

編譯依賴：編譯器處理源文件時，需按依賴關系（如頭文件包含）確定編譯順序。

DAG 與拓撲序示例

`拓撲排序的核心算法`

`Kahn算法（基于入度與隊列）`

核心思想：通過維護節點的入度（指向該節點的邊數），逐步選出入度為0的節點（無前置依賴），并減少其鄰接節點的入度，直至所有節點被處理或檢測到環。

`算法步驟`

1. 計算入度：遍歷圖，記錄每個節點的入度。

2. 初始化隊列：將所有入度為0的節點加入隊列。

3. 生成拓撲序：

- 出隊一個節點，加入拓撲序。

- 對該節點的所有鄰接節點，入度減1；若入度變為0，入隊。

4. 檢測環：若拓撲序長度小于節點總數，則圖中存在環，無拓撲序。

`基于DFS的拓撲排序`

核心思想：通過深度優先搜索，在回溯時將節點加入拓撲序（逆后序遍歷），若搜索中遇到回邊（指向已訪問但未回溯的節點），則存在環。

算法步驟：

1. 標記訪問狀態：用三個狀態標記節點：未訪問（0）、訪問中（1）、已訪問（2）。

2. 遞歸DFS：

- 若節點狀態為訪問中，檢測到環。

- 若節點未訪問，標記為訪問中，遞歸遍歷所有鄰接節點。

- 回溯時，標記節點為已訪問，加入拓撲序。

3. 逆序輸出：拓撲序為逆后序遍歷結果。

`LeetCode例題實戰`

`例題1：207. 課程表（中等）`

題目描述：你這個學期必須選修 `numCourses` 門課程，記為 `0` 到 `numCourses - 1`。給你一個數組 `prerequisites`，其中 `prerequisites[i] = [ai, bi]`，表示在選修課程 `ai` 之前必須先選修 `bi`。判斷是否可能完成所有課程的學習。

示例：

輸入：numCourses = 2, prerequisites = [[1,0]]

輸出：true（先學 0，再學 1）

輸入：numCourses = 2, prerequisites = [[1,0],[0,1]]

輸出：false（存在環 0→1→0）

`解題思路（Kahn算法）`

1. 構建圖：用鄰接表表示課程依賴關系，數組 `inDegree` 記錄每個課程的入度。

2. 初始化隊列：將入度為0的課程入隊。

3. 拓撲排序：處理隊列中的課程，減少依賴它的課程的入度，統計已處理課程數。

4. 判斷結果：若已處理課程數等于 `numCourses`，則無環，可完成；否則有環，不可完成。

`代碼實現`

import java.util.*;class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {// 1. 構建鄰接表和入度數組List<List<Integer>> adj = new ArrayList<>();int[] inDegree = new int[numCourses];for (int i = 0; i < numCourses; i++) {adj.add(new ArrayList<>());}for (int[] p : prerequisites) {int course = p[0];int pre = p[1];adj.get(pre).add(course); // pre → courseinDegree[course]++;}// 2. 初始化隊列（入度為0的課程）Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) {queue.offer(i);}}// 3. 拓撲排序int count = 0; // 已處理的課程數while (!queue.isEmpty()) {int curr = queue.poll();count++;// 處理依賴curr的課程for (int next : adj.get(curr)) {inDegree[next]--;if (inDegree[next] == 0) {queue.offer(next);}}}// 4. 判斷是否所有課程都被處理return count == numCourses;}}

復雜度分析

時間復雜度：O (V + E)，V 為節點數（課程數），E 為邊數（依賴關系數）。

空間復雜度：O (V + E)，鄰接表存儲圖，隊列存儲節點。

例題 2：210. 課程表 II（中等）

題目描述：同上題，但需返回一個可行的拓撲序；若無法完成所有課程，返回空數組。

示例：

輸入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

輸出：[0,1,2,3] 或 [0,2,1,3] 等

解題思路

在 Kahn 算法中，將出隊的節點依次加入拓撲序列表，最后若列表長度等于課程數則返回，否則返回空數組。

代碼實現

import java.util.*;class Solution {public int[] findOrder(int numCourses, int[][] prerequisites) {// 1. 構建鄰接表和入度數組List<List<Integer>> adj = new ArrayList<>();int[] inDegree = new int[numCourses];for (int i = 0; i < numCourses; i++) {adj.add(new ArrayList<>());}for (int[] p : prerequisites) {int course = p[0];int pre = p[1];adj.get(pre).add(course);inDegree[course]++;}// 2. 初始化隊列Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) {queue.offer(i);}}// 3. 拓撲排序并記錄結果List<Integer> topoOrder = new ArrayList<>();while (!queue.isEmpty()) {int curr = queue.poll();topoOrder.add(curr);for (int next : adj.get(curr)) {inDegree[next]--;if (inDegree[next] == 0) {queue.offer(next);}}}// 4. 檢查是否有環if (topoOrder.size() != numCourses) {return new int[0];}// 轉換為數組int[] result = new int[numCourses];for (int i = 0; i < numCourses; i++) {result[i] = topoOrder.get(i);}return result;}}

復雜度分析

時間復雜度：O (V + E)，同 Kahn 算法。

空間復雜度：O (V + E)，額外存儲拓撲序列表。

考研 408 例題解析

例題 1：概念辨析題（選擇題）

題目：下列關于拓撲排序的敘述中，錯誤的是（）。
A. 拓撲排序僅適用于有向無環圖（DAG）
B. 一個 DAG 的拓撲序是唯一的
C. Kahn 算法通過維護入度為 0 的節點生成拓撲序
D. 基于 DFS 的拓撲排序需檢測回邊以判斷是否有環

答案：B

解析：

A 正確：有環圖不存在拓撲序。

B 錯誤：一個 DAG 可能有多個拓撲序（如示例中的 A→B→C 和 A→D→B）。

C 正確：Kahn 算法的核心是入度管理。

D 正確：DFS 中遇到回邊（訪問中狀態的節點）說明有環。

例題 2：算法設計題（408 高頻考點）

題目：已知一個有向圖用鄰接表表示，設計一個算法判斷該圖是否為 DAG，若為 DAG 則輸出其拓撲序，否則輸出 “有環”。要求使用 Kahn 算法，并分析時間復雜度。

解題思路

數據結構：鄰接表 adj 存儲圖，數組 inDegree 存儲入度。
算法步驟：

- 計算所有節點的入度。
- 入度為 0 的節點入隊，初始化拓撲序列表。

- 處理隊列，更新入度和拓撲序，統計處理節點數。

- 若處理節點數等于總節點數，輸出拓撲序；否則輸出 “有環”。

代碼實現

import java.util.*;public class TopologicalSort {// 判斷是否為DAG并返回拓撲序，否則返回nullpublic List<Integer> isDAGAndTopoOrder(List<List<Integer>> adj, int n) {int[] inDegree = new int[n];// 計算入度for (int u = 0; u < n; u++) {for (int v : adj.get(u)) {inDegree[v]++;}}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < n; i++) {if (inDegree[i] == 0) {queue.offer(i);}}List<Integer> topoOrder = new ArrayList<>();while (!queue.isEmpty()) {int u = queue.poll();topoOrder.add(u);for (int v : adj.get(u)) {inDegree[v]--;if (inDegree[v] == 0) {queue.offer(v);}}}return topoOrder.size() == n ? topoOrder : null;}public static void main(String[] args) {// 示例：DAGint n = 4;List<List<Integer>> adj = new ArrayList<>();for (int i = 0; i < n; i++) {adj.add(new ArrayList<>());}adj.get(0).add(1);adj.get(0).add(2);adj.get(1).add(3);adj.get(2).add(3);TopologicalSort ts = new TopologicalSort();List<Integer> result = ts.isDAGAndTopoOrder(adj, n);if (result != null) {System.out.println("拓撲序：" + result); // 輸出：[0,1,2,3] 或類似} else {System.out.println("有環");}}}

復雜度分析

時間復雜度：O (V + E)，V 為節點數，E 為邊數。計算入度需 O (E)，隊列操作和入度更新共 O (V + E)。

空間復雜度：O (V + E)，鄰接表占 O (E)，隊列和拓撲序占 O (V)。

拓撲排序的擴展與應用

實際應用場景

項目管理：微軟 Project 等工具用拓撲排序安排任務依賴關系。
編譯系統：GCC 編譯器處理源文件依賴，按拓撲序編譯。
任務調度：操作系統進程調度中，按資源依賴關系確定執行順序。
課程平臺：MOOC 平臺推薦先修課程，生成學習路徑。

與其他圖算法的關聯

強連通分量（SCC）：有環圖的 SCC 可收縮為單個節點，形成 DAG 后再拓撲排序。

關鍵路徑：在帶權 DAG 中，拓撲序可高效計算最長路徑（關鍵路徑）。

最短路徑：DAG 的單源最短路徑可通過拓撲序在 O (V + E) 時間內求解。

考研 408 備考要點

核心考點：拓撲排序的適用條件、Kahn 算法步驟、環檢測方法。

重點掌握：

鄰接表的構建與入度計算。
Kahn 算法中隊列的作用及拓撲序生成邏輯。
拓撲排序與 DAG 的等價關系（存在拓撲序 ? 是 DAG）。

常見錯誤：
- 忽略入度為 0 的節點初始隊列可能為空（直接判定有環，但需確認節點數是否為 0）。

- 處理鄰接節點時漏減入度，導致算法錯誤。

總結

拓撲排序是處理有向無環圖（DAG）的核心算法，其 Kahn 算法和 DFS 算法各有優勢：Kahn 算法直觀易實現，適合求拓撲序；DFS 算法更簡潔，適合環檢測。本文通過 LeetCode 例題（課程表系列）展示了算法的實際應用，通過考研 408 例題鞏固了理論基礎，結合 SVG 圖示清晰呈現了算法流程。

掌握拓撲排序的關鍵在于：