拓撲排序(Topological Sort)演算法詳解
概述
拓撲排序(Topological Sort)是對**有向無環圖(DAG, Directed Acyclic Graph)**進行排序的演算法。排序結果是一個線性序列,使得對於圖中任意有向邊 (u, v),在排序結果中 u 都出現在 v 之前。
基本概念
應用場景
- 課程排課:某些課程有先修課程的要求
- 編譯依賴:程式模組間的編譯順序
- 任務調度:有依賴關係的任務執行順序
- Makefile 建構:檔案間的依賴關係
前提條件
- 圖必須是有向無環圖(DAG)
- 如果圖中存在環,則無法進行拓撲排序
演算法實作
方法一:Kahn 演算法(BFS 基礎)
基本思路
- 計算所有節點的入度
- 將入度為 0 的節點加入佇列
- 不斷從佇列中取出節點,並減少其相鄰節點的入度
- 如果相鄰節點的入度變為 0,則加入佇列
- 重複直到佇列為空
實作代碼
|
|
方法二:DFS 基礎
基本思路
- 對每個未訪問的節點進行 DFS
- 在 DFS 回溯時將節點加入結果
- 反轉結果得到拓撲排序
實作代碼
|
|
實際應用題型
1. 課程安排(LeetCode 207 & 210)
問題 207:判斷是否可以完成所有課程。
|
|
問題 210:返回課程安排的順序。
|
|
2. 所有可能的菜譜(LeetCode 2115)
問題描述:給定可製作的菜譜、所需原料以及現有原料,找出所有可能製作的菜譜。
|
|
複雜度分析
演算法 | 時間複雜度 | 空間複雜度 | 優點 | 缺點 |
---|---|---|---|---|
Kahn (BFS) | O(V + E) | O(V) | 實作簡單,易於理解 | 需要額外的入度陣列 |
DFS | O(V + E) | O(V) | 可以檢測環,記憶體使用較少 | 實作稍複雜 |
其中 V 是節點數,E 是邊數。
實作技巧
1. 環的檢測
|
|
2. 多個拓撲排序解
如果需要找出所有可能的拓撲排序:
|
|
總結
拓撲排序是處理有依賴關係問題的重要演算法。掌握要點:
- 適用條件:只能用於有向無環圖
- 兩種方法:Kahn 演算法(BFS)和 DFS 方法
- 環的檢測:兩種方法都能檢測圖中是否存在環
- 實際應用:課程安排、任務調度、編譯依賴等
選擇演算法時:
- Kahn 演算法:邏輯直觀,適合初學者
- DFS 方法:更靈活,能提供更多信息(如完成時間)