圖文詳解 DFS 和 BFS

原文連結

一、前言

深度優先周遊（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);
        }
    }
}           

三、習題演練

接下來我們來看看在 leetcode 中出現的一些使用 DFS，BFS 來解題的題目:

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

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

3
   / \
  9  20
    /  \
   15   7           

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

解題思路：這題比較簡單，隻不過是深度優先周遊的一種變形，隻要遞歸求出左右子樹的最大/最小深度即可，深度怎麼求，每遞歸調用一次函數，深度加一。不難寫出如下代碼

/**
 * 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: 給你一個二叉樹，請你傳回其按層序周遊得到的節點值。（即逐層地，從左到右通路所有節點）。示例，給定二叉樹：[3,9,20,null,null,15,7]

3
   / \
  9  20
    /  \
   15   7           

傳回其層次周遊結果：

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

解題思路：顯然這道題是廣度優先周遊的變種，隻需要在廣度優先周遊的過程中，把每一層的節點都添加到同一個數組中即可，問題的關鍵在于周遊同一層節點前，必須事先算出同一層的節點個數有多少（即隊列已有元素個數），因為 BFS 用的是隊列來實作的，周遊過程中會不斷把左右子節點入隊，這一點切記！動圖如下

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

Java 代碼

/**
 * leetcdoe 102: 二叉樹的層序周遊, 使用 bfs
 * @param root
 */
private static List<List<Integer>> bfsWithBinaryTreeLevelOrderTraversal(Node root) {
    if (root == null) {
        // 根節點為空，說明二叉樹不存在，直接傳回空數組
        return Arrays.asList();
    }
    // 最終的層序周遊結果
    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();
        // 周遊目前層的節點
        for (int i = 0; i < levelNum; i++) {
            Node node = queue.poll();
            // 隊首節點的左右子節點入隊,由于 levelNum 是在入隊前算的，是以入隊的左右節點并不會在目前層被周遊到
            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 = []  #嵌套清單，儲存最終結果
        if root is None:
            return res
        
        from collections import deque
        que = deque([root])  #隊列，儲存待處理的節點
        while len(que)!=0:
            lev = []  #清單，儲存該層的節點的值
            thislevel = len(que)  #該層節點個數
            while thislevel!=0:
                head = que.popleft()  #彈出隊首節點
                #隊首節點的左右孩子入隊
                if head.left is not None:
                    que.append(head.left)
                if head.right is not None:
                    que.append(head.right)
                lev.append(head.val)  #隊首節點的值壓入本層
                thislevel-=1
            res.append(lev)
        return res           

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

用 DFS 怎麼處理呢，我們知道， DFS 可以用遞歸來實作，其實隻要在遞歸函數上加上一個「層」的變量即可，隻要節點屬于這一層，則把這個節點放入相當層的數組裡，代碼如下：

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);
    // 周遊左結點
    dfs(root.left, level + 1);
    // 周遊右結點
    dfs(root.right, level + 1);
}           

四、DFS，BFS 在搜尋引擎中的應用

我們幾乎每天都在 Google, Baidu 這些搜尋引擎，那大家知道這些搜尋引擎是怎麼工作的嗎，簡單來說有三步

1、網頁抓取

搜尋引擎通過爬蟲将網頁爬取，獲得頁面 HTML 代碼存入資料庫中

2、預處理

索引程式對抓取來的頁面資料進行文字提取，中文分詞，（倒排）索引等處理，以備排名程式使用

3、排名

使用者輸入關鍵詞後，排名程式調用索引資料庫資料，計算相關性，然後按一定格式生成搜尋結果頁面。

我們重點看下第一步，網頁抓取。

這一步的大緻操作如下：給爬蟲配置設定一組起始的網頁，我們知道網頁裡其實也包含了很多超連結，爬蟲爬取一個網頁後，解析提取出這個網頁裡的所有超連結，再依次爬取出這些超連結，再提取網頁超連結。。。，如此不斷重複就能不斷根據超連結提取網頁。如下圖示

如上所示，最終構成了一張圖，于是問題就轉化為了如何周遊這張圖，顯然可以用深度優先或廣度優先的方式來周遊。

如果是廣度優先周遊，先依次爬取第一層的起始網頁，再依次爬取每個網頁裡的超連結，如果是深度優先周遊，先爬取起始網頁 1，再爬取此網頁裡的連結...，爬取完之後，再爬取起始網頁 2...

實際上爬蟲是深度優先與廣度優先兩種政策一起用的，比如在起始網頁裡，有些網頁比較重要（權重較高），那就先對這個網頁做深度優先周遊，周遊完之後再對其他（權重一樣的）起始網頁做廣度優先周遊。

五、總結

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

來源 | 碼海

作者 | 碼海