101北一女中 資訊選手培訓營 深度優先搜尋(DFS)的進階應用 2012.07.15 Nan

拓樸排序 Topological sort

“比我深的所有點(我的子孫)都一定在我的後面” (不是唯一解) 最前 最後 要有這個順序，這張圖必須是個DAG。

有向無環圖DAG Directed Acyclic Graph

那我們要怎麼用DFS 來做拓樸排序呢?

回顧一下…… D: 深度 1 3 2 4 6 5 D = 0 1 堆疊 Stack

回顧一下…… D: 深度 1 3 2 4 6 5 D = 0 D = 1 2 1

回顧一下…… D: 深度 1 3 2 4 6 5 D = 0 D = 1 4 D = 2 2 1

回顧一下…… D: 深度 1 3 2 4 6 5 D = 0 D = 1 D = 2 2 1

回顧一下…… D: 深度 1 3 2 4 6 5 D = 0 D = 1 6 D = 2 D = 2 2 1

回顧一下…… D: 深度 1 3 2 4 6 5 D = 3 D = 0 D = 1 3 6 D = 2 D = 2 2 1

回顧一下…… D: 深度 1 3 2 4 6 5 D = 3 D = 0 D = 1 6 D = 2 D = 2 2 1

回顧一下…… D: 深度 1 3 2 4 6 5 D = 3 D = 0 D = 1 D = 3 5 6 D = 2 D = 2 2 1

回顧一下…… D: 深度 1 3 2 4 6 5 D = 3 D = 0 D = 1 D = 3 6 D = 2 D = 2 2 1

回顧一下…… D: 深度 1 3 2 4 6 5 D = 3 D = 0 D = 1 D = 3 D = 2 D = 2 2 1

回顧一下…… D: 深度 1 3 2 4 6 5 D = 3 D = 0 D = 1 D = 3 D = 2 D = 2 1

回顧一下…… D: 深度 走訪順序：1 2 4 6 3 5 1 3 D = 3 D = 0 5 2 D = 1 D = 3 6 D = 2

換成有向圖 D: 深度 1 3 2 4 6 5 D = 0

換成有向圖 D: 深度 1 3 2 4 6 5 D = 0 D = 1

換成有向圖 D: 深度 1 3 D = 0 5 2 D = 1 6 4 D = 2 4不會在往下走了，之後只有可能存在走的到它的點  4可以當拓樸排序的最後的點

換成有向圖 D: 深度 1 3 2 4 6 5 D = 0 D = 1 D = 2 D = 2

換成有向圖 D: 深度 3不會在往下走了，之後只有可能存在走的到它的點 D = 3  3可以當拓樸排序的倒數 第二個點 1 3 D = 0  3可以當拓樸排序的倒數 第二個點 D = 3 D: 深度 1 3 2 4 6 5 D = 0 D = 1 D = 2 D = 2

換成有向圖 D: 深度 5不會在往下走了，之後只有可能存在走的到它的點 D = 3  5可以當拓樸排序的倒數 第三個點 1 3 D = 0  5可以當拓樸排序的倒數 第三個點 D = 3 D: 深度 1 3 2 4 6 5 D = 0 D = 1 D = 3 D = 2 D = 2

換成有向圖 D: 深度 D = 3 1 3 D = 0 5 2 D = 1 D = 3 6 D = 2 4 D = 2 6的小孩都走完了~  6可以當拓樸排序的倒數 第四個點

換成有向圖 D: 深度 D = 3 1 3 D = 0 5 2 D = 1 D = 3 2的小孩都走完了~ 4 6 5 D = 0 D = 1 D = 3 2的小孩都走完了~  2可以當拓樸排序的倒數 第五個點 D = 2 D = 2

換成有向圖 D: 深度 D = 3 1 3 D = 0 1的小孩都走完了~  1可以當拓樸排序的倒數 第六個點 5 2 D = 1 4 6 5 D = 0 1的小孩都走完了~  1可以當拓樸排序的倒數 第六個點 D = 1 D = 3 D = 2 D = 2

換成有向圖 D: 深度 剛剛的順序: 4 3 5 6 2 1 倒過來就是拓樸排序: 1 2 6 5 3 4 D = 3 1 3 D = 0

我們不會知道最前的點在哪 不過可以透過這樣的方式 讓整個順序還是對的 int N = # node; int map[N+1][N+1] = {{…},{…},…}; int visited[N+1] = {0}; int topo[N+1]; int topoN = 0; void dfs(int id){ int i; for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) { visited[i] = 1; dfs(i); } topo[topoN++] = id; int main(){ if ( visited[i] == 1 ) continue; for ( i = topoN - 1 ; i >= 0 ; i-- ) printf(“%d ”, topo[i]); putchar(10); 我們不會知道最前的點在哪 不過可以透過這樣的方式 讓整個順序還是對的

Strongly Connected Component, SCC

先從什麼是connected component(CC)開始… 無向邊 在同一個CC上的任兩點一定有路徑相通 可以用DFS來找(想想看為什麼?)

SCC 從無向邊變成有向邊 不能單純只用DFS (想想看為什麼?)

Kosaraju's Algorithm 先算出拓樸排序 把原圖的邊反向 從拓樸排序最前面的點開始做DFS，每做一次可走到的點就是在同一個SCC上

int N = # node; int map[N+1][N+1] = {{…},{…},…}; int visited[N+1] = {0}; int topo[N+1]; int topoN = 0; int sccID[N+1]; void dfs(int id){ int i; for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) { visited[i] = 1; dfs(i); } topo[topoN++] = id; void kosaraju(int id, int scc_id){ sccID[id] = scc_id; if ( map[i][id] == 1 && visited[i] == 0 ) {

int main(){ int i, sccN = 0; for ( i = 1 ; i <= N ; i++ ){ if ( visited[i] == 1 ) continue; visited[i] = 1; dfs(i); } visited[i] = 0; for ( i = topoN - 1 ; i >= 0 ; i-- ){ kosaraju(i, sccN++); printf(“The number of SCCs is %d\n”, sccN); 亦可參考DJWS的演算法筆記: http://www.csie.ntnu.edu.tw/~u91029/Connectivity.html#a4