Download presentation
Presentation is loading. Please wait.
1
深度優先搜尋(DFS)與 廣度優先搜尋(BFS)
101北一女中 資訊選手培訓營 深度優先搜尋(DFS)與 廣度優先搜尋(BFS) Nan
2
學了圖論基礎後….what’s next?
3
走訪 - Traversal 給你一張圖，把所有的節點走過一次的方法，我們稱為圖的走訪 (Graph Traversal)
走訪可以有任意順序，但是特定的順序會產生特定的性質。 最常用的走訪有兩種： 深度優先搜尋 (Depth First Search, DFS) 廣度優先搜尋 (Breath First Search, BFS)
4
舉個例子來說 1 3 2 4 6 5
5
深度優先搜尋 D: 深度 1 3 2 4 6 5 D = 0 1 堆疊 Stack
6
深度優先搜尋 D: 深度 1 3 2 4 6 5 D = 0 D = 1 2 1
7
深度優先搜尋 D: 深度 1 3 2 4 6 5 D = 0 D = 1 4 D = 2 2 1
8
深度優先搜尋 D: 深度 1 3 2 4 6 5 D = 0 D = 1 D = 2 2 1
9
深度優先搜尋 D: 深度 1 3 2 4 6 5 D = 0 D = 1 6 D = 2 D = 2 2 1
10
深度優先搜尋 D: 深度 1 3 2 4 6 5 D = 3 D = 0 D = 1 3 6 D = 2 D = 2 2 1
11
深度優先搜尋 D: 深度 1 3 2 4 6 5 D = 3 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 D = 3 5 6 D = 2 D = 2 2 1
13
深度優先搜尋 D: 深度 1 3 2 4 6 5 D = 3 D = 0 D = 1 D = 3 6 D = 2 D = 2 2 1
14
深度優先搜尋 D: 深度 1 3 2 4 6 5 D = 3 D = 0 D = 1 D = 3 D = 2 D = 2 2 1
15
深度優先搜尋 D: 深度 1 3 2 4 6 5 D = 3 D = 0 D = 1 D = 3 D = 2 D = 2 1
16
深度優先搜尋 D: 深度 走訪順序：1 2 4 6 3 5 1 3 D = 3 D = 0 5 2 D = 1 D = 3 6 D = 2
17
實作 通常都用遞迴來實作 你剛剛看到的堆疊會因此隱藏起來(遞迴會有系統的堆疊)
習慣上會把map、visited(紀錄有沒有被走過的、以及其他相關資訊放到global變數，讓遞迴能夠存取。
18
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);
![int N = # node; int map[N+1][N+1] = {{…},{…},…}; int visited[N+1] = {0}; int depth[N+1]; void dfs(int id){](http://slidesplayer.com/slide/15864279/88/images/18/int+N+%3D+%23+node%3B+int+map%5BN%2B1%5D%5BN%2B1%5D+%3D+%7B%7B%E2%80%A6%7D%2C%7B%E2%80%A6%7D%2C%E2%80%A6%7D%3B+int+visited%5BN%2B1%5D+%3D+%7B0%7D%3B+int+depth%5BN%2B1%5D%3B+void+dfs%28int+id%29%7B.jpg "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);")
19
堆疊 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 堆疊
![堆疊 visited[1] = 1; depth[1] = 0; dfs(1); 1 3 dfs(2) D =](http://slidesplayer.com/slide/15864279/88/images/19/%E5%A0%86%E7%96%8A+visited%5B1%5D+%3D+1%3B+depth%5B1%5D+%3D+0%3B+dfs%281%29%3B+1+3+dfs%282%29+D+%3D.jpg "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); dfs(2) D = 堆疊.")
20
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
21
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
22
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
23
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
![void dfs(int id){ int i; for ( i = 1 ; i <= N ; i++ ){ if ( map[id][i] == 1 && visited[i] == 0 ) {](http://slidesplayer.com/slide/15864279/88/images/23/void+dfs%28int+id%29%7B+int+i%3B+for+%28+i+%3D+1+%3B+i+%3C%3D+N+%3B+i%2B%2B+%29%7B+if+%28+map%5Bid%5D%5Bi%5D+%3D%3D+1+%26%26+visited%5Bi%5D+%3D%3D+0+%29+%7B.jpg "visited[i] = 1; depth[i] = depth[id] + 1; dfs(i); dfs(6) dfs(3) D = 0. D = D = 2. D =")
24
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
25
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
26
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
27
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
28
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
29
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
30
return回到 main裡的dfs(1)後，等於完成~
3 2 4 6 5 D = 3 D = 0 D = 1 D = 3 D = 2 D = 2 print出來的：
31
你可能有聽過所謂的“暴搜” DFS的變化型，本來是只找一種走法把圖走過，變成試過所有走法
關鍵點在於: 自己的鄰居都走完return回來後，把自己設回沒有走過。 或者反過來說是每個鄰居下去走過以後，設回沒走過 通常需要一個暫存的陣列放置目前走訪的順序，走到底再一次印出
32
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);
![int N = # node; int map[N+1][N+1] = {{…},{…},…}; int visited[N+1] = {0}; int path[N+1]; void dfs(int id, int depth){](http://slidesplayer.com/slide/15864279/88/images/32/int+N+%3D+%23+node%3B+int+map%5BN%2B1%5D%5BN%2B1%5D+%3D+%7B%7B%E2%80%A6%7D%2C%7B%E2%80%A6%7D%2C%E2%80%A6%7D%3B+int+visited%5BN%2B1%5D+%3D+%7B0%7D%3B+int+path%5BN%2B1%5D%3B+void+dfs%28int+id%2C+int+depth%29%7B.jpg "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);")
33
廣度優先搜尋 D: 深度 1 3 2 4 6 5 D = 0 1 佇列(Queue)
34
廣度優先搜尋 D: 深度 1 3 2 4 6 5 D = 1 D = 0 D = 1 1 2 3
35
廣度優先搜尋 D: 深度 咖啡色：已經走過 橘色：目前所在位置 皮膚色：已在queue中 粉紅色：此次加入queue 1 3 2 4 6 5
36
廣度優先搜尋 D: 深度 咖啡色：已經走過 橘色：目前所在位置 皮膚色：已在queue中 粉紅色：此次加入queue 1 3 2 4 6 5
37
廣度優先搜尋 D: 深度 咖啡色：已經走過 橘色：目前所在位置 皮膚色：已在queue中 粉紅色：此次加入queue 1 3 2 4 6 5
38
廣度優先搜尋 D: 深度 咖啡色：已經走過 橘色：目前所在位置 皮膚色：已在queue中 粉紅色：此次加入queue 1 3 2 4 6 5
39
廣度優先搜尋 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
40
廣度優先搜尋 D: 深度 走訪順序：1 2 3 4 6 5 1 3 D = 2 D = 0 D = 3 5 2 D = 1 6 D = 2
41
實做(通常直接在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++; }
![實做(通常直接在main裡) int N = # nodes; int q[N * N + 1];](http://slidesplayer.com/slide/15864279/88/images/41/%E5%AF%A6%E5%81%9A%28%E9%80%9A%E5%B8%B8%E7%9B%B4%E6%8E%A5%E5%9C%A8main%E8%A3%A1%29+int+N+%3D+%23+nodes%3B+int+q%5BN+%2A+N+%2B+1%5D%3B.jpg "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++; }")
42
實做(棋盤式地圖) 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++; }
![實做(棋盤式地圖) int way_x[4] = {1, -1, 1, -1};](http://slidesplayer.com/slide/15864279/88/images/42/%E5%AF%A6%E5%81%9A%28%E6%A3%8B%E7%9B%A4%E5%BC%8F%E5%9C%B0%E5%9C%96%29+int+way_x%5B4%5D+%3D+%7B1%2C+-1%2C+1%2C+-1%7D%3B.jpg "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++; }")
43
BFS的特性 將同一層的所有節點走完，才會走向下一層 走出來的會是最短路徑(假設邊的weight = 1) 用Queue來輔助
時間複雜度O(V + E)
44
DFS vs. BFS 1 3 1 3 5 5 2 2 6 6 4 4
45
DFS vs. BFS 1 1 2 3 2 4 4 6 6 5 5 3
Similar presentations
