前言

深度優(yōu)先遍歷(Depth First Search, 簡稱 DFS) 與廣度優(yōu)先遍歷(Breath First Search)是圖論中兩種非常重要的算法，生產(chǎn)上廣泛用于拓撲排序，尋路(走迷宮)，搜索引擎，爬蟲等，也頻繁出現(xiàn)在 leetcode，高頻面試題中。

本文將會從以下幾個方面來講述深度優(yōu)先遍歷，廣度優(yōu)先遍歷，相信大家看了肯定會有收獲。

• 深度優(yōu)先遍歷，廣度優(yōu)先遍歷簡介
• 習(xí)題演練
• DFS，BFS 在搜索引擎中的應(yīng)用

深度優(yōu)先遍歷，廣度優(yōu)先遍歷簡介

深度優(yōu)先遍歷

主要思路是從圖中一個未訪問的頂點 V 開始，沿著一條路一直走到底，然后從這條路盡頭的節(jié)點回退到上一個節(jié)點，再從另一條路開始走到底...，不斷遞歸重復(fù)此過程，直到所有的頂點都遍歷完成，它的特點是不撞南墻不回頭，先走完一條路，再換一條路繼續(xù)走。

樹是圖的一種特例(連通無環(huán)的圖就是樹)，接下來我們來看看樹用深度優(yōu)先遍歷該怎么遍歷。

1、我們從根節(jié)點 1 開始遍歷，它相鄰的節(jié)點有 2，3，4，先遍歷節(jié)點 2，再遍歷 2 的子節(jié)點 5，然后再遍歷 5 的子節(jié)點 9。

2、上圖中一條路已經(jīng)走到底了(9是葉子節(jié)點，再無可遍歷的節(jié)點)，此時就從 9 回退到上一個節(jié)點 5，看下節(jié)點 5 是否還有除 9 以外的節(jié)點，沒有繼續(xù)回退到 2，2 也沒有除 5 以外的節(jié)點，回退到 1，1 有除 2 以外的節(jié)點 3，所以從節(jié)點 3 開始進行深度優(yōu)先遍歷，如下：

3、同理從 10 開始往上回溯到 6, 6 沒有除 10 以外的子節(jié)點，再往上回溯，發(fā)現(xiàn) 3 有除 6 以外的子點 7，所以此時會遍歷 7。

3、從 7 往上回溯到 3， 1，發(fā)現(xiàn) 1 還有節(jié)點 4 未遍歷，所以此時沿著 4， 8 進行遍歷,這樣就遍歷完成了。

完整的節(jié)點的遍歷順序如下(節(jié)點上的的藍色數(shù)字代表)：

相信大家看到以上的遍歷不難發(fā)現(xiàn)這就是樹的前序遍歷,實際上不管是前序遍歷，還是中序遍歷，亦或是后序遍歷，都屬于深度優(yōu)先遍歷。

那么深度優(yōu)先遍歷該怎么實現(xiàn)呢，有遞歸和非遞歸兩種表現(xiàn)形式，接下來我們以二叉樹為例來看下如何分別用遞歸和非遞歸來實現(xiàn)深度優(yōu)先遍歷。

1、遞歸實現(xiàn)

遞歸實現(xiàn)比較簡單，由于是前序遍歷，所以我們依次遍歷當(dāng)前節(jié)點，左節(jié)點，右節(jié)點即可，對于左右節(jié)點來說，依次遍歷它們的左右節(jié)點即可，依此不斷遞歸下去，直到葉節(jié)點(遞歸終止條件)，代碼如下：

public class Solution { 
    private static class Node { 
        /** 
         * 節(jié)點值 
         */ 
        public int value; 
        /** 
         * 左節(jié)點 
         */ 
        public Node left; 
        /** 
         * 右節(jié)點 
         */ 
        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; 
        } 
        // 遍歷節(jié)點 
        process(treeNode) 
        // 遍歷左節(jié)點 
        dfs(treeNode.left); 
        // 遍歷右節(jié)點 
        dfs(treeNode.right); 
    } 
} 

遞歸的表達性很好，也很容易理解，不過如果層級過深，很容易導(dǎo)致棧溢出。所以我們重點看下非遞歸實現(xiàn)。

2、非遞歸實現(xiàn)

仔細觀察深度優(yōu)先遍歷的特點，對二叉樹來說，由于是先序遍歷(先遍歷當(dāng)前節(jié)點，再遍歷左節(jié)點，再遍歷右節(jié)點)，所以我們有如下思路：

對于每個節(jié)點來說，先遍歷當(dāng)前節(jié)點，然后把右節(jié)點壓棧，再壓左節(jié)點(這樣彈棧的時候會先拿到左節(jié)點遍歷，符合深度優(yōu)先遍歷要求)。

彈棧，拿到棧頂?shù)墓?jié)點，如果節(jié)點不為空，重復(fù)步驟 1， 如果為空，結(jié)束遍歷。

我們以以下二叉樹為例來看下如何用棧來實現(xiàn) DFS。

整體動圖如下：

整體思路還是比較清晰的，使用棧來將要遍歷的節(jié)點壓棧，然后出棧后檢查此節(jié)點是否還有未遍歷的節(jié)點，有的話壓棧，沒有的話不斷回溯(出棧)，有了思路，不難寫出如下用棧實現(xiàn)的二叉樹的深度優(yōu)先遍歷代碼：

/** 
 * 使用棧來實現(xiàn) dfs 
 * @param root 
 */ 
public static void dfsWithStack(Node root) { 
    if (root == null) { 
        return; 
    } 
 
    Stack<Node> stack = new Stack<>(); 
    // 先把根節(jié)點壓棧 
    stack.push(root); 
    while (!stack.isEmpty()) { 
        Node treeNode = stack.pop(); 
        // 遍歷節(jié)點 
        process(treeNode) 
 
        // 先壓右節(jié)點 
        if (treeNode.right != null) { 
            stack.push(treeNode.right); 
        } 
 
        // 再壓左節(jié)點 
        if (treeNode.left != null) { 
            stack.push(treeNode.left); 
        } 
    } 
} 

可以看到用棧實現(xiàn)深度優(yōu)先遍歷其實代碼也不復(fù)雜，而且也不用擔(dān)心遞歸那樣層級過深導(dǎo)致的棧溢出問題。

廣度優(yōu)先遍歷

廣度優(yōu)先遍歷，指的是從圖的一個未遍歷的節(jié)點出發(fā)，先遍歷這個節(jié)點的相鄰節(jié)點，再依次遍歷每個相鄰節(jié)點的相鄰節(jié)點。

上文所述樹的廣度優(yōu)先遍歷動圖如下，每個節(jié)點的值即為它們的遍歷順序。所以廣度優(yōu)先遍歷也叫層序遍歷，先遍歷第一層(節(jié)點 1)，再遍歷第二層(節(jié)點 2，3，4)，第三層(5，6，7，8)，第四層(9，10)。

深度優(yōu)先遍歷用的是棧，而廣度優(yōu)先遍歷要用隊列來實現(xiàn)，我們以下圖二叉樹為例來看看如何用隊列來實現(xiàn)廣度優(yōu)先遍歷。

動圖如下：

相信看了以上動圖，不難寫出如下代碼：

/** 
 * 使用隊列實現(xiàn) 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); 
        } 
    } 
} 

習(xí)題演練

接下來我們來看看在 leetcode 中出現(xiàn)的一些使用 DFS，BFS 來解題的題目：

leetcode 104，111: 給定一個二叉樹，找出其最大/最小深度。 

例如：給定二叉樹 [3,9,20,null,null,15,7],

   3 
  / \ 
 9  20 
   /  \ 
  15   7 

則它的最小深度 2，最大深度 3。

解題思路：這題比較簡單，只不過是深度優(yōu)先遍歷的一種變形，只要遞歸求出左右子樹的最大/最小深度即可，深度怎么求，每遞歸調(diào)用一次函數(shù)，深度加一。不難寫出如下代碼：

/** 
 * leetcode 104: 求樹的最大深度 
 * @param node 
 * @return 
 */ 
public static int getMaxDepth(Node node) { 
    if (node == null) { 
        return 0; 
    } 
    int leftDepth = getMaxDepth(node.left) + 1; 
    int rightDepth = getMaxDepth(node.right) + 1; 
    return Math.max(leftDepth, rightDepth); 
} 
 
/** 
 * leetcode 111: 求樹的最小深度 
 * @param node 
 * @return 
 */ 
public static int getMinDepth(Node node) { 
    if (node == null) { 
        return 0; 
    } 
    int leftDepth = getMinDepth(node.left) + 1; 
    int rightDepth = getMinDepth(node.right) + 1; 
    return Math.min(leftDepth, rightDepth); 
} 

leetcode 102: 給你一個二叉樹，請你返回其按層序遍歷得到的節(jié)點值。(即逐層地，從左到右訪問所有節(jié)點)。示例，給定二叉樹：[3,9,20,null,null,15,7]。

   3 
  / \ 
 9  20 
   /  \ 
  15   7 

返回其層次遍歷結(jié)果：

[ 
  [3], 
  [9,20], 
  [15,7] 
] 

解題思路：顯然這道題是廣度優(yōu)先遍歷的變種，只需要在廣度優(yōu)先遍歷的過程中，把每一層的節(jié)點都添加到同一個數(shù)組中即可，問題的關(guān)鍵在于遍歷同一層節(jié)點前，必須事先算出同一層的節(jié)點個數(shù)有多少(即隊列已有元素個數(shù))，因為 BFS 用的是隊列來實現(xiàn)的，遍歷過程中會不斷把左右子節(jié)點入隊，這一點切記!動圖如下：

根據(jù)以上動圖思路不難得出代碼如下：

Java 代碼

/** 
 * leetcdoe 102: 二叉樹的層序遍歷, 使用 bfs 
 * @param root 
 */ 
private static List<List<Integer>> bfsWithBinaryTreeLevelOrderTraversal(Node root) { 
    if (root == null) { 
        // 根節(jié)點為空，說明二叉樹不存在，直接返回空數(shù)組 
        return Arrays.asList(); 
    } 
 
    // 最終的層序遍歷結(jié)果 
    List<List<Integer>> result = new ArrayList<>(); 
 
    Queue<Node> queue = new LinkedList<>(); 
    queue.offer(root); 
 
    while (!queue.isEmpty()) { 
        // 記錄每一層 
        List<Integer> level = new ArrayList<>(); 
        int levelNum = queue.size(); 
        // 遍歷當(dāng)前層的節(jié)點 
        for (int i = 0; i < levelNum; i++) { 
            Node node = queue.poll(); 
            // 隊首節(jié)點的左右子節(jié)點入隊,由于 levelNum 是在入隊前算的，所以入隊的左右節(jié)點并不會在當(dāng)前層被遍歷到 
            if (node.left != null) { 
                queue.add(node.left); 
            } 
            if (node.right != null) { 
                queue.add(node.right); 
            } 
            level.add(node.value); 
        } 
        result.add(level); 
    } 
 
    return result; 
} 

Python 代碼

class Solution: 
    def levelOrder(self, root): 
        """ 
        :type root: TreeNode 
        :rtype: List[List[int]] 
        """ 
        res = []  #嵌套列表，保存最終結(jié)果 
        if root is None: 
            return res 
         
        from collections import deque 
        que = deque([root])  #隊列，保存待處理的節(jié)點 
        while len(que)!=0: 
            lev = []  #列表，保存該層的節(jié)點的值 
            thislevel = len(que)  #該層節(jié)點個數(shù) 
            while thislevel!=0: 
                head = que.popleft()  #彈出隊首節(jié)點 
                #隊首節(jié)點的左右孩子入隊 
                if head.left is not None: 
                    que.append(head.left) 
                if head.right is not None: 
                    que.append(head.right) 
                lev.append(head.val)  #隊首節(jié)點的值壓入本層 
                thislevel-=1 
            res.append(lev) 
        return res 

這題用 BFS 是顯而易見的，但其實也可以用 DFS， 如果在面試中能用 DFS 來處理，會是一個比較大的亮點。

用 DFS 怎么處理呢，我們知道， DFS 可以用遞歸來實現(xiàn)，其實只要在遞歸函數(shù)上加上一個「層」的變量即可，只要節(jié)點屬于這一層，則把這個節(jié)點放入相當(dāng)層的數(shù)組里，代碼如下：

private static final List<List<Integer>> TRAVERSAL_LIST  = new ArrayList<>(); 
/** 
 * leetcdoe 102: 二叉樹的層序遍歷, 使用 dfs 
 * @param root 
 * @return 
 */ 
private static void dfs(Node root, int level) { 
    if (root == null) { 
        return; 
    } 
 
    if (TRAVERSAL_LIST.size() < level + 1) { 
        TRAVERSAL_LIST.add(new ArrayList<>()); 
    } 
 
    List<Integer> levelList = TRAVERSAL_LIST.get(level); 
    levelList.add(root.value); 
 
    // 遍歷左結(jié)點 
    dfs(root.left, level + 1); 
 
    // 遍歷右結(jié)點 
    dfs(root.right, level + 1); 
} 

DFS，BFS 在搜索引擎中的應(yīng)用我們幾乎每天都在 Google, Baidu 這些搜索引擎，那大家知道這些搜索引擎是怎么工作的嗎，簡單來說有三步：

1、網(wǎng)頁抓取

搜索引擎通過爬蟲將網(wǎng)頁爬取，獲得頁面 HTML 代碼存入數(shù)據(jù)庫中

2、預(yù)處理

索引程序?qū)ψト淼捻撁鏀?shù)據(jù)進行文字提取，中文分詞，(倒排)索引等處理，以備排名程序使用

3、排名

用戶輸入關(guān)鍵詞后，排名程序調(diào)用索引數(shù)據(jù)庫數(shù)據(jù)，計算相關(guān)性，然后按一定格式生成搜索結(jié)果頁面。

我們重點看下第一步，網(wǎng)頁抓取。

這一步的大致操作如下：給爬蟲分配一組起始的網(wǎng)頁，我們知道網(wǎng)頁里其實也包含了很多超鏈接，爬蟲爬取一個網(wǎng)頁后，解析提取出這個網(wǎng)頁里的所有超鏈接，再依次爬取出這些超鏈接，再提取網(wǎng)頁超鏈接。。。，如此不斷重復(fù)就能不斷根據(jù)超鏈接提取網(wǎng)頁。如下圖示：

如上所示，最終構(gòu)成了一張圖，于是問題就轉(zhuǎn)化為了如何遍歷這張圖，顯然可以用深度優(yōu)先或廣度優(yōu)先的方式來遍歷。

如果是廣度優(yōu)先遍歷，先依次爬取第一層的起始網(wǎng)頁，再依次爬取每個網(wǎng)頁里的超鏈接，如果是深度優(yōu)先遍歷，先爬取起始網(wǎng)頁 1，再爬取此網(wǎng)頁里的鏈接...，爬取完之后，再爬取起始網(wǎng)頁 2...

實際上爬蟲是深度優(yōu)先與廣度優(yōu)先兩種策略一起用的，比如在起始網(wǎng)頁里，有些網(wǎng)頁比較重要(權(quán)重較高)，那就先對這個網(wǎng)頁做深度優(yōu)先遍歷，遍歷完之后再對其他(權(quán)重一樣的)起始網(wǎng)頁做廣度優(yōu)先遍歷。

總結(jié)

DFS 和 BFS 是非常重要的兩種算法，大家一定要掌握，本文為了方便講解，只對樹做了 DFS，BFS，大家可以試試如果用圖的話該怎么寫代碼，原理其實也是一樣，只不過圖和樹兩者的表示形式不同而已，DFS 一般是解決連通性問題，而 BFS 一般是解決最短路徑問題，之后有機會我們會一起來學(xué)習(xí)下并查集，Dijkstra, Prism 算法等，敬請期待!