深度優先搜尋(DFS)與 廣度優先搜尋(BFS) 101北一女中 資訊選手培訓營 深度優先搜尋(DFS)與 廣度優先搜尋(BFS) 2012.07.08 Nan

學了圖論基礎後….what’s next?

走訪 - Traversal 給你一張圖，把所有的節點走過一次的方法，我們稱為圖的走訪 (Graph Traversal) 走訪可以有任意順序，但是特定的順序會產生特定的性質。 最常用的走訪有兩種： 深度優先搜尋 (Depth First Search, DFS) 廣度優先搜尋 (Breath First Search, BFS)

舉個例子來說 1 3 2 4 6 5

深度優先搜尋 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

實作 通常都用遞迴來實作 你剛剛看到的堆疊會因此隱藏起來(遞迴會有系統的堆疊) 習慣上會把map、visited(紀錄有沒有被走過的、以及其他相關資訊放到global變數，讓遞迴能夠存取。

int N = # node; int map[N+1][N+1] = {{…},{…},…}; int visited[N+1] = {0}; int depth[N+1]; void dfs(int id){ int i; printf(“%d\n”, id); for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) { visited[i] = 1; depth[i] = depth[id] + 1; dfs(i); } int main(){ visited[1] = 1; depth[1] = 0; dfs(1);

堆疊 visited[1] = 1; depth[1] = 0; dfs(1); 1 3 dfs(2) D = 0 5 2 6 4 1 void dfs(int id){ int i; for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) { visited[i] = 1; depth[i] = depth[id] + 1; dfs(i); visited[1] = 1; depth[1] = 0; dfs(1); 1 3 2 4 6 5 dfs(2) D = 0 1 堆疊

dfs(2) 1 dfs(4) 3 D = 0 5 2 D = 1 6 4 2 1 void dfs(int id){ int i; for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) { visited[i] = 1; depth[i] = depth[id] + 1; dfs(i); dfs(2) 1 3 2 4 6 5 dfs(4) D = 0 D = 1 2 1

dfs(4) 1 結束!return! 3 會回到dfs(2)時的for迴圈繼續跑 D = 0 5 2 D = 1 6 4 D = 2 4 void dfs(int id){ int i; for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) { visited[i] = 1; depth[i] = depth[id] + 1; dfs(i); dfs(4) 1 3 2 4 6 5 結束!return! 會回到dfs(2)時的for迴圈繼續跑 D = 0 D = 1 4 D = 2 2 1

return回到 dfs(4) 1 dfs(6) 3 D = 0 5 2 D = 1 6 D = 2 4 2 1 void dfs(int id){ int i; for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) { visited[i] = 1; depth[i] = depth[id] + 1; dfs(i); return回到 dfs(4) 1 3 2 4 6 5 dfs(6) D = 0 D = 1 D = 2 2 1

void dfs(int id){ int i; for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) { visited[i] = 1; depth[i] = depth[id] + 1; dfs(i); dfs(6) 1 3 2 4 6 5 dfs(3) D = 0 D = 1 6 D = 2 D = 2 2 1

dfs(3) 1 結束!return! 3 D = 3 會回到dfs(6)時的for迴圈繼續跑 D = 0 5 2 D = 1 6 3 6 void dfs(int id){ int i; for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) { visited[i] = 1; depth[i] = depth[id] + 1; dfs(i); dfs(3) 1 3 2 4 6 5 結束!return! 會回到dfs(6)時的for迴圈繼續跑 D = 3 D = 0 D = 1 3 6 D = 2 D = 2 2 1

return回到 dfs(6) 1 dfs(5) 3 D = 3 D = 0 5 2 D = 1 6 6 D = 2 D = 2 4 2 1 void dfs(int id){ int i; for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) { visited[i] = 1; depth[i] = depth[id] + 1; dfs(i); return回到 dfs(6) 1 3 2 4 6 5 dfs(5) D = 3 D = 0 D = 1 6 D = 2 D = 2 2 1

dfs(5) 1 結束!return! 3 D = 3 會回到dfs(6)時的for迴圈繼續跑 D = 0 5 2 D = 1 D = 3 void dfs(int id){ int i; for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) { visited[i] = 1; depth[i] = depth[id] + 1; dfs(i); dfs(5) 1 3 2 4 6 5 結束!return! 會回到dfs(6)時的for迴圈繼續跑 D = 3 D = 0 D = 1 D = 3 5 6 D = 2 D = 2 2 1

return回到 dfs(6) 1 結束!return! 3 D = 3 會回到dfs(2)時的for迴圈繼續跑 D = 0 5 2 void dfs(int id){ int i; for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) { visited[i] = 1; depth[i] = depth[id] + 1; dfs(i); return回到 dfs(6) 1 3 2 4 6 5 結束!return! 會回到dfs(2)時的for迴圈繼續跑 D = 3 D = 0 D = 1 D = 3 6 D = 2 D = 2 2 1

return回到 dfs(2) 1 結束!return! 3 D = 3 會回到dfs(1)時的for迴圈繼續跑 D = 0 5 2 void dfs(int id){ int i; for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) { visited[i] = 1; depth[i] = depth[id] + 1; dfs(i); return回到 dfs(2) 1 3 2 4 6 5 結束!return! 會回到dfs(1)時的for迴圈繼續跑 D = 3 D = 0 D = 1 D = 3 D = 2 D = 2 2 1

return回到 dfs(1) 1 結束!return! 3 D = 3 會回到main去 結束! D = 0 5 2 D = 1 void dfs(int id){ int i; for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) { visited[i] = 1; depth[i] = depth[id] + 1; dfs(i); return回到 dfs(1) 1 3 2 4 6 5 結束!return! 會回到main去 結束! D = 3 D = 0 D = 1 D = 3 D = 2 D = 2 1

return回到 main裡的dfs(1)後，等於完成~ 3 2 4 6 5 D = 3 D = 0 D = 1 D = 3 D = 2 D = 2 print出來的：1 2 4 6 3 5

你可能有聽過所謂的“暴搜” DFS的變化型，本來是只找一種走法把圖走過，變成試過所有走法 關鍵點在於: 自己的鄰居都走完return回來後，把自己設回沒有走過。 或者反過來說是每個鄰居下去走過以後，設回沒走過 通常需要一個暫存的陣列放置目前走訪的順序，走到底再一次印出

int N = # node; int map[N+1][N+1] = {{…},{…},…}; int visited[N+1] = {0}; int path[N+1]; void dfs(int id, int depth){ int i; if ( depth >= N ){ for ( i = 0 ; i < N ; i++ ) printf(“ %d”, path[i]); putchar(‘\n’); return; } for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) { visited[i] = 1; path[depth] = i; dfs(i, depth + 1); visited[i] = 0; // 還原! int main(){ visited[1] = 1; path[0] = 1; dfs(1, 1);

廣度優先搜尋 D: 深度 1 3 2 4 6 5 D = 0 1 佇列(Queue)

廣度優先搜尋 D: 深度 1 3 2 4 6 5 D = 1 D = 0 D = 1 1 2 3

廣度優先搜尋 D: 深度 咖啡色：已經走過 橘色：目前所在位置 皮膚色：已在queue中 粉紅色：此次加入queue 1 3 2 4 6 5

廣度優先搜尋 D: 深度 咖啡色：已經走過 橘色：目前所在位置 皮膚色：已在queue中 粉紅色：此次加入queue 1 3 2 4 6 5

廣度優先搜尋 D: 深度 咖啡色：已經走過 橘色：目前所在位置 皮膚色：已在queue中 粉紅色：此次加入queue 1 3 2 4 6 5

廣度優先搜尋 D: 深度 咖啡色：已經走過 橘色：目前所在位置 皮膚色：已在queue中 粉紅色：此次加入queue 1 3 2 4 6 5

廣度優先搜尋 D: 深度 咖啡色：已經走過 橘色：目前所在位置 皮膚色：已在queue中 粉紅色：此次加入queue 1 3 D = 2 4 6 5 D = 2 D = 0 D = 3 D = 1 咖啡色：已經走過 橘色：目前所在位置 皮膚色：已在queue中 粉紅色：此次加入queue D = 2 D = 2 5

廣度優先搜尋 D: 深度 走訪順序：1 2 3 4 6 5 1 3 D = 2 D = 0 D = 3 5 2 D = 1 6 D = 2

實做(通常直接在main裡) int N = # nodes; int q[N * N + 1]; int map[N+1][N+1] = {{…},{…},…}; int visited[N+1] = {0}; int head, tail = 0; int i; q[0] = 1; visited[1] = 1; for(head=0; head<tail; head++) { for(i=1; i<=N; i++) if(visited[i] == 0 && map[q[head]][i] == 1) q[tail] = i; tail++; }

實做(棋盤式地圖) int way_x[4] = {1, -1, 1, -1}; int way_y[4] = {1, 1, -1, -1}; for(head=0; head<tail; head++) { for(i=0; i<4; i++) if(map[qx[head] + way_x[i]][qy[head] + way_y[i]]) map[qx[head] + way_x[i]][qy[head] + way_y[i]] = 1; qx[tail] = qx[head] + way_x[i]; qy[tail] = qy[head] + way_y[i]; qn[tail] = qn[head] + 1; tail++; }

BFS的特性 將同一層的所有節點走完，才會走向下一層 走出來的會是最短路徑(假設邊的weight = 1) 用Queue來輔助 時間複雜度O(V + E)

DFS vs. BFS 1 3 1 3 5 5 2 2 6 6 4 4

DFS vs. BFS 1 1 2 3 2 4 4 6 6 5 5 3