上文中我們了解了圖的遍歷(DFS/BFS), 本節我們來學習拓撲排序.
在圖論中, 拓撲排序(Topological Sorting)是對一個有向無環圖(Directed Acyclic Graph, DAG)的所有頂點進行排序的一種算法, 使得如果存在一條從頂點 u 到頂點 v 的有向邊 (u, v) , 那么在排序后的序列中, u 一定在 v 之前.
環境要求
本文所用樣例在Windows 11以及Ubuntu 24.04上面編譯通過.
- Windows: 使用[Visual Studio],
- Ubuntu: 使用 Clang 18.1.3. (Ubuntu 24.04 系統安裝版本)
- GCC 無法編譯直接本項目代碼, 因為本文代碼使用了 C++20 Module, 而 GCC 對此支持不完整.
關于 Module 的更多信息, 請參考我之前的博客: CMake 構建 C++20 Module 實例(使用 MSVC)
本項目工程目錄: 圖論代碼
適用場景
拓撲排序適用于需要確定一系列任務的執行順序, 且任務之間存在依賴關系的場景. 下圖是是一個示例圖, 其中頂點代表任務, 有向邊代表依賴(A -> B 意味著A 需要在 B 之前完成). 拓撲排序就是給出任務能夠完成的先后順序.
算法實現
常見的拓撲排序算法有兩種: Kahn 算法和深度優先搜索(DFS)算法.
Kahn 算法
- 統計每個頂點的入度(即指向該頂點的邊的數量).
- 將所有入度為 0 的頂點加入隊列中.
- 從隊列中取出一個頂點, 將其輸出, 并將該頂點的所有鄰接頂點的入度減 1.
- 如果某個鄰接頂點的入度變為 0, 則將其加入隊列中.
- 重復步驟 3 和 4, 直到隊列為空.
- 如果輸出的頂點數量小于圖中的頂點總數, 則說明圖中存在環, 無法進行拓撲排序.
過程步驟如圖:
- 起初, 入度為 0 的頂點為
A,F. 我們可以彈出A和F中的任意一個. 這里假設我們先彈出A.
- 彈出
A后, 邊線A -> B和A -> C被彈出, 并且入度B和C分別減 1, 此時狀態如圖所示. 接下來我們要彈出F.
- 彈出
F后, 邊線F -> C被彈出, 并且入度C減 1, 此時狀態如圖所示. 接下來我們彈出B.
- 彈出
B后, 邊線B -> D被彈出, 并且入度D減 1, 此時狀態如圖所示. 接下來我們彈出C.
- 彈出
C后, 邊線C -> D被彈出, 并且入度D減 1, 此時狀態如圖所示. 接下來我們彈出D.
- 彈出
D后, 邊線D -> E被彈出, 并且入度E減 1, 此時狀態如圖所示. 接下來我們彈出E.
- 彈出
E后, 隊列為空, 算法結束.
代碼實現
class TopologicalSortKahn {public:explicit TopologicalSortKahn(const AdjList& graph) : graph_(graph) {if (!graph_.Directed()) {throw std::invalid_argument("Graph must be directed for topological sorting.");}}std::vector<
