第05講：深度與廣度優先搜索 · 300分鐘搞定數據結構與算法

這節課重點學習深度優先搜索算法（簡稱為 DFS）和廣度優先搜索算法（簡稱為 BFS）。 DFS 和 BFS 經常在算法面試題當中出現，在整個算法面試知識點中所占的比重非常大。應用最多的地方就是對圖進行遍歷，樹也是圖的一種。 #### 深度優先搜索（Depth-First Search / DFS）深度優先搜索，從起點出發，從規定的方向中選擇其中一個不斷地向前走，直到無法繼續為止，然后嘗試另外一種方向，直到最后走到終點。就像走迷宮一樣，盡量往深處走。 DFS 解決的是連通性的問題，即，給定兩個點，一個是起始點，一個是終點，判斷是不是有一條路徑能從起點連接到終點。起點和終點，也可以指的是某種起始狀態和最終的狀態。問題的要求并不在乎路徑是長還是短，只在乎有還是沒有。有時候題目也會要求把找到的路徑完整的打印出來。 * [ ] DFS 遍歷例題：假設我們有這么一個圖，里面有A、B、C、D、E、F、G、H 8 個頂點，點和點之間的聯系如下圖所示，對這個圖進行深度優先的遍歷。 * [ ] 解題思路必須依賴棧（Stack），特點是后進先出（LIFO）。第一步，選擇一個起始頂點，例如從頂點 A 開始。把 A 壓入棧，標記它為訪問過（用紅色標記），并輸出到結果中。 ? 第二步，尋找與 A 相連并且還沒有被訪問過的頂點，頂點 A 與 B、D、G 相連，而且它們都還沒有被訪問過，我們按照字母順序處理，所以將 B 壓入棧，標記它為訪問過，并輸出到結果中。第三步，現在我們在頂點 B 上，重復上面的操作，由于 B 與 A、E、F 相連，如果按照字母順序處理的話，A 應該是要被訪問的，但是 A 已經被訪問了，所以我們訪問頂點 E，將 E 壓入棧，標記它為訪問過，并輸出到結果中。第四步，從 E 開始，E 與 B、G 相連，但是B剛剛被訪問過了，所以下一個被訪問的將是G，把G壓入棧，標記它為訪問過，并輸出到結果中。第五步，現在我們在頂點 G 的位置，由于與 G 相連的頂點都被訪問過了，類似于我們走到了一個死胡同，必須嘗試其他的路口了。所以我們這里要做的就是簡單地將 G 從棧里彈出，表示我們從 G 這里已經無法繼續走下去了，看看能不能從前一個路口找到出路。可以看到，每次我們在考慮下一個要被訪問的點是什么的時候，如果發現周圍的頂點都被訪問了，就把當前的頂點彈出。第六步，現在棧的頂部記錄的是頂點 E，我們來看看與 E 相連的頂點中有沒有還沒被訪問到的，發現它們都被訪問了，所以把 E 也彈出去。? 第七步，當前棧的頂點是 B，看看它周圍有沒有還沒被訪問的頂點，有，是頂點 F，于是把 F 壓入棧，標記它為訪問過，并輸出到結果中。第八步，當前頂點是 F，與 F 相連并且還未被訪問到的點是 C 和 D，按照字母順序來，下一個被訪問的點是 C，將 C 壓入棧，標記為訪問過，輸出到結果中。? ? 第九步，當前頂點為 C，與 C 相連并尚未被訪問到的頂點是 H，將 H 壓入棧，標記為訪問過，輸出到結果中。 ? 第十步，當前頂點是 H，由于和它相連的點都被訪問過了，將它彈出棧。 ? 第十一步，當前頂點是 C，與 C 相連的點都被訪問過了，將 C 彈出棧。第十二步，當前頂點是 F，與 F 相連的并且尚未訪問的點是 D，將 D 壓入棧，輸出到結果中，并標記為訪問過。?? 第十三步，當前頂點是 D，與它相連的點都被訪問過了，將它彈出棧。以此類推，頂點 F，B，A 的鄰居都被訪問過了，將它們依次彈出棧就好了。最后，當棧里已經沒有頂點需要處理了，我們的整個遍歷結束。 ? ? ? ?? ? **例題分析一** 給定一個二維矩陣代表一個迷宮，迷宮里面有通道，也有墻壁，通道由數字 0 表示，而墻壁由 -1 表示，有墻壁的地方不能通過，那么，能不能從 A 點走到 B 點。從 A 開始走的話，有很多條路徑通往 B，例如下面兩種。 ? ? ? ?? * [ ] 代碼實現根據例題，來看實現代碼，如下。 ``` boolean?dfs(int?maze[][],?int?x,?int?y)?{ ????//?第一步：判斷是否找到了B ????if?(x?==?B[0]?&&?y?==?B[1])?{ ????????return?true; ????}? ????//?第二步：標記當前的點已經被訪問過 ????maze[x][y]?=?-1; ????//?第三步：在四個方向上嘗試 ????for?(int?d?=?0;?d?<?4;?d++)?{ ????????int?i?=?x?+?dx[d],?j?=?y?+?dy[d]; ????????//?第四步：如果有一條路徑被找到了，返回true ????????if?(isSafe(maze,?i,?j)?&&?dfs(maze,?i,?j))?{ ????????????return?true; ????????} ????} ????//?付出了所有的努力還是沒能找到B，返回false ????return?false; ?? } ``` * [ ] 非遞歸實現遞歸實現： * 代碼看上去很簡潔； * 實際應用中，遞歸需要壓入和彈出棧，棧深的時候會造成運行效率低下。非遞歸實現： * 棧支持壓入和彈出； * 棧能提高效率。代碼實現 ``` boolean?dfs(int?maze[][],?int?x,?int?y)?{ ????//?創建一個Stack ????Stack<Integer[]>?stack?=?new?Stack<>(); ????//?將起始點壓入棧，標記它訪問過 ????stack.push(new?Integer[]?{x,?y}); ????maze[x][y]?=?-1; ???? ????while?(!stack.isEmpty())?{ ????????//?取出當前點 ????????Integer[]?pos?=?stack.pop(); ????????x?=?pos[0];?y?=?pos[1]; ?????? ????????//?判斷是否找到了目的地 ????????if?(x?==?B[0]?&&?y?==?B[1])?{ ??????????return?true; ????????} ???? ????????//?在四個方向上嘗試?? ????????for?(int?d?=?0;?d?<?4;?d++)?{ ????????????int?i?=?x?+?dx[d],?j?=?y?+?dy[d]; ???????????? ????????if?(isSafe(maze,?i,?j))?{ ????????????stack.push(new?Integer[]?{i,?j}); ????????????maze[i][j]?=?-1; ????????????} ????????} ????} ????return?false; } ``` **算法分析** DFS 是圖論里的算法，分析利用 DFS 解題的復雜度時，應當借用圖論的思想。圖有兩種表示方式：鄰接表、鄰接矩陣。假設圖里有 V 個頂點，E 條邊。時間復雜度： * 鄰接表訪問所有頂點的時間為 O(V)，而查找所有頂點的鄰居一共需要 O(E) 的時間，所以總的時間復雜度是 O(V + E)。 * 鄰接矩陣查找每個頂點的鄰居需要 O(V) 的時間，所以查找整個矩陣的時候需要?O(V2)?的時間。舉例：利用 DFS 在迷宮里找一條路徑的復雜度。迷宮是用矩陣表示。解法：把迷宮看成是鄰接矩陣。假設矩陣有 M 行 N 列，那么一共有 M × N 個頂點，因此時間復雜度就是 O(M × N)。空間復雜度： DFS 需要堆棧來輔助，在最壞情況下，得把所有頂點都壓入堆棧里，所以它的空間復雜度是 O(V)，即 O(M × N)。 * 例題分析二例題：利用 DFS 去尋找最短的路徑。解題思路思路 1：暴力法。尋找出所有的路徑，然后比較它們的長短，找出最短的那個。此時必須嘗試所有的可能。因為 DFS 解決的只是連通性問題，不是用來求解最短路徑問題的。思路 2：優化法。一邊尋找目的地，一邊記錄它和起始點的距離（也就是步數）。從某方向到達該點所需要的步數更少，則更新。從各方向到達該點所需要的步數都更多，則不再嘗試。 ? ? 代碼實現 ``` void?solve(int?maze[][])?{ ????//?第一步.?除了A之外，將其他等于0的地方用MAX_VALUE替換 ????for?(int?i?=?0;?i?<?maze.length;?i++)?{ ????????for?(int?j?=?0;?j?<?maze[0].length;?j++)?{ ?? ????if?(maze[i][j]?==?0?&&?!(i?==?A[0]?&&?j?==?A[1]))?{ ????????????????maze[i][j]?=?Integer.MAX_VALUE; ????????????} ????????} ????} ????//?第二步.?進行優化的DFS操作 ????dfs(maze,?A[0],?A[1]); ????//?第三步.?看看是否找到了目的地 ????if?(maze[B[0]][B[1]]?<?Integer.MAX_VALUE)?{ ????????print("Shortest?path?count?is:?"?+?maze[B[0]][B[1]]); ????}?else?{ ??????print("Cannot?find?B!"); ????} } ????? ????void?dfs(int?maze[][],?int?x,?int?y)?{ ????????//?第一步.?判斷是否找到了B ????????if?(x?==?B[0]?&&?y?==?B[1])?return; ????????//?第二步.?在四個方向上嘗試 ????????for?(int?d?=?0;?d?<?4;?d++)?{ ????????????int?i?=?x?+?dx[d],?j?=?y?+?dy[d]; ????????????//?判斷下一個點的步數是否比目前的步數+1還要大 ????????????if?(isSafe(maze,?i,?j)?&&?maze[i][j]?>?maze[x][y]?+?1)?{ ????????????//?如果是，就更新下一個點的步數，并繼續DFS下去 ????????????????maze[i][j]?=?maze[x][y]?+?1; ????????????????dfs(maze,?i,?j); ????????????} ????????} ????} ``` 注意：之前的題目只要找到了一個路徑就返回，這里我們必須盡可能多的去嘗試，直到找到最短路徑。運行結果當程序運行完畢之后，矩陣的最終結果如下。 ``` 2,??1,??A,??1,??2,??3 3,??2,?-1,??2,??3,??4? 4,??3,?-1,??3,??4,??5? 5,??4,?-1,?-1,??5,??6? 6,?-1,??8,??7,??6,??7? 7,??8,??9,??8,??7,?-1 ``` 可以看到，矩陣中每個點的數值代表著它離 A 點最近的步數。 #### 廣度優先搜索（Breadth-First Search / BFS）廣度優先搜索，一般用來解決最短路徑的問題。和深度優先搜索不同，廣度優先的搜索是從起始點出發，一層一層地進行，每層當中的點距離起始點的步數都是相同的，當找到了目的地之后就可以立即結束。廣度優先的搜索可以同時從起始點和終點開始進行，稱之為雙端 BFS。這種算法往往可以大大地提高搜索的效率。舉例：在社交應用程序中，兩個人之間需要經過多少個朋友的介紹才能互相認識對方。解法： * 只從一個方向進行 BFS，有時候這個人認識的朋友特別多，那么會導致搜索起來非常慢； * 如果另外一方認識的人比較少，從這一方進行搜索，就能極大地減少搜索的次數； * 每次在決定從哪一邊進行搜索的時候，要判斷一下哪邊認識的人比較少，然后從那邊進行搜索。 **BFS 遍歷** 例題：假設我們有這么一個圖，里面有A、B、C、D、E、F、G、H 8 個頂點，點和點之間的聯系如下圖所示，對這個圖進行深度優先的遍歷。 ? ? ? ?? ? **解題思路** 依賴隊列（Queue），先進先出（FIFO）。一層一層地把與某個點相連的點放入隊列中，處理節點的時候正好按照它們進入隊列的順序進行。第一步，選擇一個起始頂點，讓我們從頂點 A 開始。把 A 壓入隊列，標記它為訪問過（用紅色標記）。 ? 第二步，從隊列的頭取出頂點 A，打印輸出到結果中，同時將與它相連的尚未被訪問過的點按照字母大小順序壓入隊列，同時把它們都標記為訪問過，防止它們被重復地添加到隊列中。第三步，從隊列的頭取出頂點 B，打印輸出它，同時將與它相連的尚未被訪問過的點（也就是 E 和 F）壓入隊列，同時把它們都標記為訪問過。第四步，繼續從隊列的頭取出頂點 D，打印輸出它，此時我們發現，與 D 相連的頂點 A 和 F 都被標記訪問過了，所以就不要把它們壓入隊列里。? ? 第五步，接下來，隊列的頭是頂點 G，打印輸出它，同樣的，G 周圍的點都被標記訪問過了。我們不做任何處理。第六步，隊列的頭是 E，打印輸出它，它周圍的點也都被標記為訪問過了，我們不做任何處理。第七步，接下來輪到頂點 F，打印輸出它，將 C 壓入隊列，并標記 C 為訪問過。第八步，將 C 從隊列中移出，打印輸出它，與它相連的 H 還沒被訪問到，將 H 壓入隊列，將它標記為訪問過。 ? ?? ? ?第九步，隊列里只剩下 H 了，將它移出，打印輸出它，發現它的鄰居都被訪問過了，不做任何事情。第十步，隊列為空，表示所有的點都被處理完畢了，程序結束。 * [ ] 例題分析一運用廣度優先搜索的算法在迷宮中尋找最短的路徑。 **解題思路** 搜索的過程如下。從起始點 A 出發，類似于漣漪，一層一層地掃描，避開墻壁，同時把每個點與 A 的距離或者步數標記上。當找到目的地的時候返回步數，這個步數保證是最短的。代碼實現 ``` void?bfs(int[][]?maze,?int?x,?int?y)?{ ????//?創建一個隊列queue，將起始點A加入隊列中 ????Queue<Integer[]>?queue?=?new?LinkedList<>(); ????queue.add(new?Integer[]?{x,?y}); ?? ????//?只要隊列不為空就一直循環下去?? ????while?(!queue.isEmpty())?{ ????????//?從隊列的頭取出當前點 ????????Integer[]?pos?=?queue.poll(); ????????x?=?pos[0];?y?=?pos[1]; ?????? ????????//?從四個方向進行BFS ????????for?(int?d?=?0;?d?<?4;?d++)?{ ????????????int?i?=?x?+?dx[d],?j?=?y?+?dy[d]; ???????? ????????????if?(isSafe(maze,?i,?j))?{ ????????????????//?記錄步數（標記訪問過） ????????????????maze[i][j]?=?maze[x][y]?+?1; ????????????????//?然后添加到隊列中?? ????????????????queue.add(new?Integer[]?{i,?j}); ????????????????//?如果發現了目的地就返回?? ????????????????if?(i?==?B[0]?&&?j?==?B[1])?return; ????????????} ????????} ????} } ``` * [ ] 算法分析同樣借助圖論的分析方法，假設有 V 個頂點，E 條邊。時間復雜度： * 鄰接表每個頂點都需要被訪問一次，時間復雜度是 O(V)；相連的頂點（也就是每條邊）也都要被訪問一次，加起來就是 O(E)。因此整體時間復雜度就是 O(V+E)。 * 鄰接矩陣 V 個頂點，每次都要檢查每個頂點與其他頂點是否有聯系，因此時間復雜度是?O(V2)。舉例：在迷宮里進行 BFS 搜索。解法：用鄰接矩陣。假設矩陣有 M 行 N 列，那么一共有 M×N 個頂點，時間復雜度就是 O(M×N)。空間復雜度：需要借助一個隊列，所有頂點都要進入隊列一次，從隊列彈出一次。在最壞的情況下，空間復雜度是 O(V)，即 O(M×N)。 * [ ] 例題分析二例題：假設從起始點 A 走到目的地 B 的過程中，最多允許打通 3 堵墻，求最短的路徑的步數。（這個題目可以擴展到允許打通任意數目的墻。） * [ ] 解題思路 * 思路 1：暴力法。 1. 首先枚舉出所有拆墻的方法. 假設一共有 K 堵墻在當前的迷宮里，最多允許拆 3 堵墻，有四種情況：不拆，只拆一堵墻、兩堵墻、三堵墻。組合方式如下。 ``` C(K, 0) + C(K, 1) + C(K, 2) + C(K, 3) = 1 + K + K ×(K - 1) / 2 + K× (K - 1) ×(K - 2) / 6 ``` 上式復雜度為 K 的 3 次方，如果允許打通墻的數量是 w，那么就是 K 的 w 次方。 2. 分別進行 BFS，整體的時間復雜度就是?O(n2×Kw)，從中找到最短的那條路徑。很顯然，該方法非常沒有效率。 * 思路 2： 1. 將 BFS 的數量減少。 * 在不允許打通墻的情況下，只有一個人進行 BFS 搜索，時間復雜度是?n2； * 允許打通一堵墻的情況下，分身為兩個人進行 BFS 搜索，時間復雜度是 2×n2； * 允許打通兩堵墻的情況下，分身為三個人進行 BFS 搜索，時間復雜度是 3×n2； * 允許打通三堵墻的情況下，分身為四個人進行 BFS 搜索，時間復雜度是 4×n2。? 2. 解決關鍵問題。 * 如果第一個人又遇到了一堵墻，那么他是否需要再次分身呢？不能。 * 第一個人怎么告訴第二個人可以去訪問這個點？把這個點放入到隊列中。 * 如何讓 4 個人在獨立的平面里搜索？利用一個三維矩陣記錄每個層面里的點。只需要 4 個人去做 BFS，整體的時間復雜度就是 4 倍的 BFS。代碼實現 ``` int?bfs(int[][]?maze,?int?x,?int?y,?int?w)?{ ????//?初始化 ????int?steps?=?0,?z?=?0; ????//?利用隊列來輔助BFS ????Queue<Integer[]>?queue?=?new?LinkedList<>(); ????queue.add(new?Integer[]?{x,?y,?z}); ????queue.add(null); ????//?三維的visited記錄各層平面中每個點是否被訪問過 ????boolean[][][]?visited?=?new?boolean[N][N][w?+?1]; ????visited[x][y][z]?=?true;?? ????//?只要隊列不為空就一直循環 ????while?(!queue.isEmpty())?{ ????????Integer[]?pos?=?queue.poll(); ?????? ????????if?(pos?!=?null)?{ ????????????//?取出當前點 ????????????x?=?pos[0];?y?=?pos[1];?z?=?pos[2]; ????????????//?如果遇到了目的地就立即返回步數 ????????????if?(x?==?B[0]?&&?y?==?B[1])?{ ??????????????return?steps; ????????????} ???????? ????????//?朝四個方向嘗試 ????????for?(int?d?=?0;?d?<?4;?d++)?{ ????????????int?i?=?x?+?dx[d],?j?=?y?+?dy[d]; ?????????? ????????????if?(!isSafe(maze,?i,?j,?z,?visited))?{ ????????????????continue; ????????????} ?????????? ????????????//?如果在當前層遇到了墻，嘗試打通它 ????????????int?k?=?getLayer(maze,?w,?i,?j,?z); ?????????? ????????????if?(k?>=?0)?{ ????????????????//?如果能打通墻，就在下一層嘗試 ????????????????visited[i][j][k]?=?true; ????????????????queue.add(new?Integer[]?{i,?j,?k}); ????????????} ????????} ??????}?else?{ ????????steps++; ???????? ????????if?(!queue.isEmpty())?{ ????????????queue.add(null); ????????} ??????} ????} ???? ????return?-1; } ``` 注意： * 初始化隊列的時候，除了把在第一層里的起始點 A 加入到隊列中，還加入了一個 null，這是使用 BFS 的一個小技巧，用來幫助我們計算當前遍歷了多少步數。 * 其中，利用 getLayer 函數判斷是否遇到了墻壁，以及是否能打通墻壁到下一層。 * 最后，如果當前點是 null，表明已經處理完當前的步數，繼續下一步。 getLayer 函數的代碼實現如下。 ``` int?getLayer(int[][]?maze,?int?w,?int?x,?int?y,?int?z)?{ ????if?(maze[x][y]?==?-1)?{ ????????return?z?<?w???z?+?1?:?-1; ????} ????return?z; } ``` getLayer 的思想很簡單，如果當前遇到的是一堵墻，那么看打通的墻壁個數是否已經超出了規定，如果沒有，就繼續打通它，否則返回 -1。另外，如果當前遇到的不是一堵墻，就繼續在當前的平面里進行 BFS。 #### 結語這節課學習了深度優先和廣度優先這兩種搜索算法。它們都是算法面試中常考的知識點。建議對二者比較學習。 LeetCode 上對 DFS 以及 BFS 有非常好的分類和題庫，而且對于時間復雜度和空間復雜度都有考察，是很好的練手的平臺，希望大家多多練習。