拓樸排序 - HackMD

# 拓樸排序 Topological Sort 拓樸排序是一種幫一張圖上的節點做線性排序的演算法。對於一張有向無環圖中的所有節點 $V(G) = \{v_1,v_2,...,v_{|V|}\}$，排出一個序列，使所有有向邊 $(u,v) \in E(G)$ 在序列中 $u$ 必排在 $v$ 之前 ## 為什麼需要拓樸排序? 為什麼會需要這個演算法呢? 可以考慮以下問題: ### 引入情境 :::info 已知資工系有 $10$ 門課程: |課程 1|課程 2|課程 3|課程 4|課程 5| | ----- | ----- | ----- | ----- | ----- | |計算機概論|電腦網路|離散數學|微積分|演算法| |課程 6|課程 7|課程 8|課程 9|課程 10| | ----- | ----- | ----- | ----- | ----- | |深度學習|機率論|資料結構|計算機組織|數位邏輯| 每一門課程都有優先修習的順序，如下圖 ```graphviz digraph hierarchy { size ="4,4" 計算機概論 -> 資料結構 -> 演算法 -> 深度學習離散數學 -> 數位邏輯 -> 計算機組織離散數學 -> 資料結構演算法 -> 電腦網路微積分 -> 機率論 -> 深度學習 } ``` 以上圖為例，如果想要修習「演算法」，就得先修「資料結構」... 以此類推如果某大一新生想排修課順序把 $10$ 門課都修完，該如何排安排才能符合以上規則呢? ::: ### 解法我們把問題拆解一下: 假設我只想修「資料結構」，那麼先決條件就是需要先修完「離散數學」與「計算機概論」在此問題中，其中一種合理的順序是: **計算機概論、微積分、離散數學、數位邏輯、資料結構、計算機組織、演算法、電腦網路、機率論、深度學習** 當然，我們也可以發現答案不只一種，像是以下也可以是一種解答: **微積分、計算機概論、離散數學、數位邏輯、資料結構、計算機組織、演算法、電腦網路、機率論、深度學習** ### 小結這個問題相當簡單，看一下就能知道答案。因為它只有 $10$ 門課，在圖論而言，就是 $10$ 個節點但是如果今天問題變成有 $10^{6}$ 個節點呢? 太多了吧!! 這顯然需要一套「規則」去解決這個問題 ## 介紹 ### 目標拓樸排序可以為一張是 $dag$ 的圖 $G$ 排出適當的走訪路徑，使對於 $G$ 的所有邊 $(u,v)$，$u$ 必出現在 $v$ 之前 ### 輸入/輸出 - 輸入為一張 $dag$ - 輸出則為一個陣列，紀錄節點的順序 ### 備註 - **拓樸排序以 $dag$ 作為輸入**，這是一個定理，在機制的部分會詳細說明 - $dag$ 為有向無環圖 directed acyclic graph 的簡稱 ### 拓樸??? 沒有，這一點拓樸學也沒有。在古早時代的「拓樸」一詞涵蓋的非常廣泛，基本上只要是非數字或幾何的東西都可能被冠上拓樸之稱。早期的圖論也被認為是拓樸學的內容，而現在則不一定。像是拓樸排序所排的節點順序就不是基於數字的大小關係，因此才會有「拓樸」二字出現 ## 原理說明 ### 觀察 1: 入度與 $dag$ 的關係對於 $G$ 的所有邊 $(u,v)$，$u$ 必出現在 $v$ 之前。因此必須最先選擇入度為 $0$ 的節點，因為入度為 $0$ 的節點**沒有任何邊通往此節點** 接下來要走訪鄰居節點，但是要怎麼走訪呢? 可以試著把已走訪過的節點從圖上「**刪除**」，如此一來，就會有新的入度為 $0$ 的節點了以下圖為例我們可以將 $a$ 刪除，如此一來就知道接下來要走訪 $b$，因為 $b$ 的入度為 $0$ (沒有結點走到 $b$) ```graphviz digraph hierarchy { node [shape = "circle"] size = "3,3" rankdir = LR a -> b a -> c -> d {rank=same b -> c} } ``` ⭣ ```graphviz digraph hierarchy { node [shape = "circle"] size = "2,3" rankdir = LR c -> d {rank=same b -> c} } ``` **入度: 對於一有向圖，設一節點 $v$，則 $v$ 的入度即為所有通往 $v$ 的邊數** ### 觀察 2: 深度優先 (DFS) 走訪順序在先前探討 [DFS 與 BFS](https://hackmd.io/@ShanC/bfs_dfs) 中，有提及 DFS 的「時間戳記」性質 1. 在 DFS 森林中，如果有 $(u,v)$ 存在，就不會出現 $(v,u)$，因為每個節點只被拜訪一次 2. 時間戳記中，有一陣列 $f[i]$ 紀錄節點 $i$ 完成拜訪所有鄰居的時間 3. 當一節點 $v$ 完成拜訪，即 $v$ 的所有在 DFS 森林中的所有後代都已**完成拜訪** 4. 會發現以完成時間順序由大到小排所有節點 $v$，即為拓樸排序 ## 拓樸排序的機制 (Kahn's Algorithm) 首先，這個演算法名稱是[這樣](https://youtu.be/GpFO5vfOjhI?si=T9ORP4zuoGAxrpPH)唸 ### 說明 step1. 第一個點必不會排在其他點後方，因此要找的 $v$ 必須 $deg(v) = 0$，即入度為 $0$ step2. 將每個入度為 $0$ 的節點走訪過 step3. 刪除每個入度為 $0$ 的節點，此步驟會產生新的入度為 $0$ 的節點 step4. 回到 step1. 直到沒有入度為 $0$ 的節點產生這想法看起來非常遞迴，實際上用迴圈時做即可，~~比較看得懂~~ ### 測環此方法也可以用於測定是否有環假設這張有向圖是有環的，則會有可能產生「無法走訪」的節點。因此如果在跑完此演算法之後，發現有節點未被走訪，則這是一張有環有向圖 ```graphviz digraph hierarchy { size = "3,3" rankdir = LR a -> b b -> c d -> b {rank=same c -> d} } ``` ⭣ 完成拓樸排序後 ⭣ ```graphviz digraph hierarchy { size = "3,3" rankdir = LR b -> c d -> b {rank=same c -> d} } ``` 由於沒有任何節點入度為 $0$，因此演算法停止，然而仍有三點未被刪去，因此認定此圖有環 ## 拓樸排序的機制 (DFS) 要特別說明一點，要排出順序必須要有「**大小關係**」 ### 名詞定義在 DFS 樹或是森林中: - 白點: 未被走過的節點 - 灰點: 被走過，但並未拜訪完鄰居的節點 - 黑點: 已拜訪完鄰居的節點 - 後向邊: 設 $u$ 是 $v$ 的後代，則 $u$ 連到 $v$ 的邊為後向邊 ### 引理對有向圖 $G$ 進行 DFS 不產生後向邊，若且為若，$G$ 沒有迴路 ### 定理: 拓樸排序算法能為 $dag$ 排出優先順序假設以 DFS 走訪 $dag$ $G = (V, E)$，若有一條邊 $(u, v)$，則 $f[u] > f[v]$，證明如下: 當 $(u,v)$ 邊被發現時 - 如果 $v$ 是灰點，則 $(u,v)$ 就是一條後向邊，這樣會與引理相違背，因此不可能出現 - 如果 $v$ 是白點，就代表他是 $u$ 的後代，因此 $f[u] > f[v]$ - 如果 $v$ 是黑點，則代表此 $(u, v)$ 早已被走訪完畢了，因此 $f[u] > f[v]$ 得證: 對於 $G$ 中的所有邊 $(u,v) \in E$ 而言，$f[u] > f[v]$ 由於每個節點都有「**大小關係**」，因此可以排出優先順序 ### 測環根據以上證明，當一條邊 $(u, v)$ 被發現時，如果 $v$ 是灰點，使 $(u, v)$ 為一條後向邊，則此圖有環 ## 程式實作 ### 刪除節點版本 (Kahn's Algorithm) 在實作上，不需要真的把節點刪除，只需要在走訪節點時將其鄰居的入度 $-1$ 即可其實 queue 改成 stack 也會產生一組拓樸排序的結果 #### C++ code ```cpp vector<int> edge[MAXN], ans; // MAXN: 最大節點數 int deg[MAXN]; // 入度 void topo(int n) { // 節點編號為 1-based queue<int> que; // 以 queue 當作拜訪清單 for (int i = 1; i <= n; i++) if (!deg[i]) // 如果入度 == 0 則加入此節點 que.push(i); while (!que.empty()) { int u = que.front(); que.pop(); ans.push_back(u); // 結果存 ans for (int v : edge[u]) { deg[v]--; // 每次走訪完都先幫鄰居的入度 -1 if (!deg[v]) // 如果入度 == 0 則加入此節點 que.push(v); } } } ``` #### 時間複雜度令節點數 $|V| = n$、邊數 $|E| = m$ - 遍歷整個 $deg[~]$ : $O(n)$ - 遍歷整張圖: $O(n + m)$ - 總時間複雜度: $O(n) + O(n + m) = O(n + m)$ ### DFS 版本 #### C++ code ```cpp vector<int> edge[MAXN], ans; bool vis[MAXN]; int f[MAXN], time_cnt; // MAXN: 最大節點數 void dfs(int u) { vis[u] = true; for (int v : edge[u]) { if (vis[v]) continue; dfs(v); } f[u] = ++time_cnt; // 紀錄完成拜訪的時間 ans.push_back(u); // 將順序存入 ans } void topo(int n) { // 1-base time_cnt = 0; for (int i = 1; i <= n; i++) { if (!vis[i]) dfs(i); } reverse(ans.begin(), ans.end()); // 反轉答案 } ``` #### 時間複雜度令節點數 $|V| = n$、邊數 $|E| = m$ - DFS 整張圖: $O(n + m)$ - 將答案存入 $ans$ : $O(n)$ - 反轉 $ans$ : $O(n)$ - 總時間複雜度: $O(n + m) + O(n) \times 2 = O(n + m)$ ## 題目練習 [Zerojudge f167. m4a1-社團 Club](https://zerojudge.tw/ShowProblem?problemid=f167) [CSES Course Schedule](https://cses.fi/problemset/task/1679) [UVa 200 - Rare Order](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=136) [CSES Game Routes](https://cses.fi/problemset/) [CSES Longest Flight Route](https://cses.fi/problemset/task/1680) (DP on DAG) [AtCoder dp_g - G - Longest Path](https://atcoder.jp/contests/dp/tasks/dp_g?lang=en) (DP on DAG) [Zerojudge k734. APCS 4. 開啟寶盒](https://zerojudge.tw/ShowProblem?problemid=k734) [Codeforces Contest 1385 E. Directing Edges](https://codeforces.com/contest/1385/problem/E) [Zerojudge l245. D. 汽車不再繞圈圈](https://zerojudge.tw/ShowProblem?problemid=l245) (二分搜 + 拓排 + 把DFS版本的證明讀熟就會的東西) ---- ## 參考資料 - Introduction to Algorithms, Fourth Edition - [海大競程圖論](https://hackmd.io/@LeeShoWhaodian/Graph1#/) - [geeksforgeeks](https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/) - [directed acyclic graph - 台師大演算法筆記](https://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html) - [SA 流 C++ 競程修練心法](https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FHybjt6suS) - [Why is "topological sorting" topological?](https://cstheory.stackexchange.com/questions/30659/why-is-topological-sorting-topological) - [Etymology of "topological sorting"](https://math.stackexchange.com/questions/113288/etymology-of-topological-sorting) ---- > [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC) > 作者: ShanC > 更新: 2024/11/22