前言
深度優先遍歷（Depth First Search, 簡稱 DFS） 與廣度優先遍歷（Breath First Search）是圖論中兩種非常重要的算法，生產上廣泛用於拓撲排序，尋路（走迷宮），搜索引擎，爬蟲等，也頻繁出現在 leetcode，高頻面試題中。
本文將會從以下幾個方面來講述深度優先遍歷，廣度優先遍歷，相信大家看了肯定會有收穫。
- 深度優先遍歷，廣度優先遍歷簡介
- 習題演練
- DFS，BFS 在搜索引擎中的應用
深度優先遍歷，廣度優先遍歷簡介
深度優先遍歷
深度優先遍歷主要思路是從圖中一個未訪問的頂點 V 開始，沿著一條路一直走到底，然後從這條路盡頭的節點回退到上一個節點，再從另一條路開始走到底...，不斷遞歸重複此過程，直到所有的頂點都遍歷完成，它的特點是不撞南牆不回頭，先走完一條路，再換一條路繼續走。
樹是圖的一種特例（連通無環的圖就是樹），接下來我們來看看樹用深度優先遍歷該怎麼遍歷。
1、我們從根節點 1 開始遍歷，它相鄰的節點有 2，3，4，先遍歷節點 2，再遍歷 2 的子節點 5，然後再遍歷 5 的子節點 9。
2、上圖中一條路已經走到底了（9是葉子節點，再無可遍歷的節點），此時就從 9 回退到上一個節點 5，看下節點 5 是否還有除 9 以外的節點，沒有繼續回退到 2，2 也沒有除 5 以外的節點，回退到 1，1 有除 2 以外的節點 3，所以從節點 3 開始進行深度優先遍歷，如下
3、同理從 10 開始往上回溯到 6, 6 沒有除 10 以外的子節點，再往上回溯，發現 3 有除 6 以外的子點 7，所以此時會遍歷 7
3、從 7 往上回溯到 3， 1，發現 1 還有節點 4 未遍歷，所以此時沿著 4， 8 進行遍歷,這樣就遍歷完成了
完整的節點的遍歷順序如下（節點上的的藍色數字代表）
相信大家看到以上的遍歷不難發現這就是樹的前序遍歷,實際上不管是前序遍歷，還是中序遍歷，亦或是後序遍歷，都屬於深度優先遍歷。
那麼深度優先遍歷該怎麼實現呢，有遞歸和非遞歸兩種表現形式，接下來我們以二叉樹為例來看下如何分別用遞歸和非遞歸來實現深度優先遍歷。
1、遞歸實現
遞歸實現比較簡單，由於是前序遍歷，所以我們依次遍歷當前節點，左節點，右節點即可，對於左右節點來說，依次遍歷它們的左右節點即可，依此不斷遞歸下去，直到葉節點（遞歸終止條件），代碼如下
public class Solution {
private static class Node {
/**
* 節點值
*/
public int value;
/**
* 左節點
*/
public Node left;
/**
* 右節點
*/
public Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
public static void dfs(Node treeNode) {
if (treeNode == null) {
return;
}
// 遍歷節點
process(treeNode)
// 遍歷左節點
dfs(treeNode.left);
// 遍歷右節點
dfs(treeNode.right);
}
}遞歸的表達性很好，也很容易理解，不過如果層級過深，很容易導致棧溢出。所以我們重點看下非遞歸實現
2、非遞歸實現
仔細觀察深度優先遍歷的特點，對二叉樹來說，由於是先序遍歷（先遍歷當前節點，再遍歷左節點，再遍歷右節點），所以我們有如下思路
1、對於每個節點來說，先遍歷當前節點，然後把右節點壓棧，再壓左節點（這樣彈棧的時候會先拿到左節點遍歷，符合深度優先遍歷要求）
2、彈棧，拿到棧頂的節點，如果節點不為空，重複步驟 1， 如果為空，結束遍歷。
我們以以下二叉樹為例來看下如何用棧來實現 DFS。
整體動圖如下
整體思路還是比較清晰的，使用棧來將要遍歷的節點壓棧，然後出棧後檢查此節點是否還有未遍歷的節點，有的話壓棧，沒有的話不斷回溯（出棧），有了思路，不難寫出如下用棧實現的二叉樹的深度優先遍歷代碼:
/**
* 使用棧來實現 dfs
* @param root
*/
public static void dfsWithStack(Node root) {
if (root == null) {
return;
}
Stack<Node> stack = new Stack<>();
// 先把根節點壓棧
stack.push(root);
while (!stack.isEmpty()) {
Node treeNode = stack.pop();
// 遍歷節點
process(treeNode)
// 先壓右節點
if (treeNode.right != null) {
stack.push(treeNode.right);
}
// 再壓左節點
if (treeNode.left != null) {
stack.push(treeNode.left);
}
}
}可以看到用棧實現深度優先遍歷其實代碼也不復雜，而且也不用擔心遞歸那樣層級過深導致的棧溢出問題。
廣度優先遍歷
廣度優先遍歷，指的是從圖的一個未遍歷的節點出發，先遍歷這個節點的相鄰節點，再依次遍歷每個相鄰節點的相鄰節點。
上文所述樹的廣度優先遍歷動圖如下，每個節點的值即為它們的遍歷順序。所以廣度優先遍歷也叫層序遍歷，先遍歷第一層（節點 1），再遍歷第二層（節點 2，3，4），第三層（5，6，7，8），第四層（9，10）。
深度優先遍歷用的是棧，而廣度優先遍歷要用隊列來實現，我們以下圖二叉樹為例來看看如何用隊列來實現廣度優先遍歷
動圖如下
相信看了以上動圖，不難寫出如下代碼
/**
* 使用隊列實現 bfs
* @param root
*/
private static void bfs(Node root) {
if (root == null) {
return;
}
Queue<Node> stack = new LinkedList<>();
stack.add(root);
while (!stack.isEmpty()) {
Node node = stack.poll();
System.out.println("value = " + node.value);
Node left = node.left;
if (left != null) {
stack.add(left);
}
Node right = node.right;
if (right != null) {
stack.add(right);
}
}
}DFS，BFS 在搜索引擎中的應用
我們幾乎每天都在 Google, Baidu 這些搜索引擎，那大家知道這些搜索引擎是怎麼工作的嗎，簡單來說有三步
1、網頁抓取
搜索引擎通過爬蟲將網頁爬取，獲得頁面 HTML 代碼存入數據庫中
2、預處理
索引程序對抓取來的頁面數據進行文字提取，中文分詞，（倒排）索引等處理，以備排名程序使用
3、排名
用戶輸入關鍵詞後，排名程序調用索引數據庫數據，計算相關性，然後按一定格式生成搜索結果頁面。
我們重點看下第一步，網頁抓取。
這一步的大致操作如下：給爬蟲分配一組起始的網頁，我們知道網頁裡其實也包含了很多超鏈接，爬蟲爬取一個網頁後，解析提取出這個網頁裡的所有超鏈接，再依次爬取出這些超鏈接，再提取網頁超鏈接。。。，如此不斷重複就能不斷根據超鏈接提取網頁。如下圖示
如上所示，最終構成了一張圖，於是問題就轉化為了如何遍歷這張圖，顯然可以用深度優先或廣度優先的方式來遍歷。
如果是廣度優先遍歷，先依次爬取第一層的起始網頁，再依次爬取每個網頁裡的超鏈接，如果是深度優先遍歷，先爬取起始網頁 1，再爬取此網頁裡的鏈接...，爬取完之後，再爬取起始網頁 2...
實際上爬蟲是深度優先與廣度優先兩種策略一起用的，比如在起始網頁裡，有些網頁比較重要（權重較高），那就先對這個網頁做深度優先遍歷，遍歷完之後再對其他（權重一樣的）起始網頁做廣度優先遍歷。
總結
DFS 和 BFS 是非常重要的兩種算法，大家一定要掌握，本文為了方便講解，只對樹做了 DFS，BFS，大家可以試試如果用圖的話該怎麼寫代碼，原理其實也是一樣，只不過圖和樹兩者的表示形式不同而已，DFS 一般是解決連通性問題，而 BFS 一般是解決最短路徑問題，之後有機會我們會一起來學習下並查集，Dijkstra, Prism 算法等，敬請期待！
來源 | 碼海
作者 | 碼海