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

Presentation on theme: "101北一女中 資訊選手培訓營 深度優先搜尋(DFS)的進階應用 2012.07.15 Nan."— Presentation transcript:

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

2 拓樸排序 Topological sort

3

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

5 有向無環圖DAG Directed Acyclic Graph

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23 換成有向圖 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

24 換成有向圖 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

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

26 換成有向圖 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

27 換成有向圖 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

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

29 我們不會知道最前的點在哪 不過可以透過這樣的方式 讓整個順序還是對的 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); 我們不會知道最前的點在哪 不過可以透過這樣的方式 讓整個順序還是對的

30

31 Strongly Connected Component, SCC

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

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

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

35 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 ) {

36 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的演算法筆記: