圖文詳解 DFS 算法 和 BFS 算法

2021-02-13 五分鐘學算法
前言

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

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

深度優先遍歷，廣度優先遍歷簡介 深度優先遍歷

深度優先遍歷主要思路是從圖中一個未訪問的頂點 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， 如果為空，結束遍歷。
我們以以下二叉樹為例來看下如何用棧來實現 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 算法等，敬請期待！

相關焦點

  • 圖文詳解 DFS 和 BFS
    來源：碼海作者：碼海深度優先遍歷（Depth First Search, 簡稱 DFS） 與廣度優先遍歷（Breath First Search）是圖論中兩種非常重要的算法，生產上廣泛用於拓撲排序，尋路（走迷宮），搜尋引擎，爬蟲等，也頻繁出現在 leetcode，高頻面試題中。
  • 一道題看透DFS和BFS
    作者丨小小算法來源丨小小算法（xiaoxiaosuanfa）一道題看透DFS和BFS你知道 DFS 和 BFS 是哪幾個英文單詞的縮寫嗎？(手動滑稽)。DFS: Depth First Search (深度優先搜索)BFS: Breadth First Search (廣度優先搜索)DFS 和 BFS 都是常用來遍歷搜索樹或圖的算法。
  • 從頭開始複習算法之讓你徹底搞清楚BFS和DFS
    來源：https://www.imooc.com/article/285772最近又有點學不進去了，不知道是不是天氣熱的緣故哈，沒辦法只好寫一點算法來保持學習的路線不間斷咯。關於BFS和DFS，這是我們在面試的時候經常會遇到的兩個基礎算法，為什麼說基礎呢？因為它理解了之後才10行左右的代碼，你說基礎不基礎？
  • Edmond-Karp 最大流算法詳解
    以上三篇前導文章都是在認識和使用最大流這種問題模型，從而進行一些算法思考。但是我們始終沒有關心 Ford-Fulkerson 方法的時間複雜度問題。基於 DFS 的 FF 方法複雜度分析從上面這裡例子，你已經發現了，當基於 DFS 的 FF 算法的最差情況複雜度是和最大流相關的。假設我們有 E 條邊並且最大流是 F，每次 DFS 查增廣路則需要 O(E) 的複雜度，當最大流是 E 的時候，我們要進行最多 E 次的增廣路查找。
  • Java數據結構和算法(三)圖的深度優先遍歷算法,附代碼(DFS)
    所謂圖的遍歷，即是對結點的訪問，一個圖會有很多的結點，那麼如何遍歷這些結點，需要特定的策略，一般有兩種訪問策略深度遍歷優先和廣度遍歷優先。
  • 算法小專欄開篇:DFS之Fibonaci數列
    初衷更多是為了簡單的算法知識普及吧，也是我當初做筆記的一個想法，後面出個小專欄也行。相信大家也關注了其他大佬的號，有很多講得666的文章和視頻，B站更是比比皆是，我當然會以我自己的理解來寫，不求卓越，但求無誤。
  • BFS 算法框架套路詳解
    後臺有很多人問起 BFS 和 DFS 的框架，今天就來說說吧。首先，你要說 labuladong 沒寫過 BFS 框架，這話沒錯，今天寫個框架你背住就完事兒了。但要是說沒寫過 DFS 框架，那你還真是說錯了，其實 DFS 算法就是回溯算法，我們前文 回溯算法框架套路詳解 就寫過了，而且寫得不是一般得好，建議好好複習。
  • 萬字詳述 | 全開源:python寫小遊戲+AI強化學習與傳統DFS/BFS控制分別實現
    我以我在 GitHub 上開源的項目 PiperLiu / Amazing-Brick-DFS-and-DRL 為對象，從零開始與各位朋友分享：如何用 python 寫一個小遊戲 、 如何匹配傳統的深度優先搜索算法來控制 、 如何匹配傳統的廣度優先搜索算法來控制 、 如何匹配深度強化學習算法來控制
  • 一文帶你搞懂什麼是圖以及常見的算法實現
    isVisited[i]) {dfs(isVisited, i);}}}執行結果:廣度優先遍歷(bfs)基本思想:的鄰接節點後的下一個鄰接節點,重複步驟6直到隊列為空/*** 廣度優先遍歷* @param isVisited* @param i*/private void bfs
  • 算法工程師思維導圖 | 數據結構與算法
    該手冊一共分為數據結構與算法、數學基礎、統計機器學習和深度學習四個部分。點擊這裡查看具體使用指南。該手冊有兩種獲取方式：下面是數據結構與算法部分~數據結構二維矩陣/直方圖最大距形面積矩陣最大面積：https://leetcode-cn.com/problems/maximal-rectangle/solution/zui-da-ju-xing-by-leetcode/
  • EM算法詳解
    EM算法簡介3. 預備知識    3.1 極大似然估計    3.2 Jensen不等式4. EM算法詳解    4.1 問題描述    4.2 EM算法推導流程    4.3 EM算法流程5.EM算法受到缺失思想影響，最初是為了解決數據缺失情況下的參數估計問題，其算法基礎和收斂有效性等問題在Dempster、Laird和Rubin三人於1977年所做的文章《Maximum likelihood from incomplete data via the EM algorithm》中給出了詳細的闡述。
  • 有關樹遍歷的javascript實現【前端-總結-leetcode算法題】
    在這裡插入圖片描述前言二月的第一天，總結一下近段時間刷的有關樹遍歷的leetcode算法題，希望寫完這篇文章的我和看完文章的你都有些收穫吧。全篇主要講的是有關樹的遍歷，使用前端javascript語言實現。當然有關樹的操作還有很多需要的深入理解和總結的。今天就暫時先把樹遍歷理解全吧。
  • 算法之深度優先搜索
    本文作者：丹丘生文末閱讀原文獲取文中示例代碼一、引言研究算法，寫算法是很枯燥的過程；但是找到規律以及通用之處，會發現它是如此簡單個人喜歡循序漸進，從小問題引出要用的算法；深度優先搜索和廣度優先搜索是搜索算法裡面比較基礎的算法，理解以及實現非常容易，當然說歸說，如何容易，且看下文。
  • KMP算法圖文詳解
    KMP算法是解決字符串匹配的常用算法之一，也就是在主串（比如aabbccdd）中的子串（bc）定位問題。子串稱為P，如果它在一個主串稱為T中出現，就返回它的具體位置，我們先來看看普通的字符串匹配是怎麼做的最基礎的匹配思路：從左到右一個個匹配，如果這個過程中有某個字符不匹配，將子串向右移動一位，繼續從左到右一一匹配。
  • codeforces 2020年12月月賽算法比賽
    零、背景這周日在 codeforces 上參加了某高校 12 月份的校賽，涉及到不少算法，分享給大家。比賽原始碼：https://github.com/tiankonguse/ACM/tree/master/codeforces/gym/306556A. 暴打出題人題意：給一個數組 n 個數字，挑選若干個數字的和可以組成一個數字。
  • 目標檢測算法YOLO-V1算法詳解
    ❝前面我們一起學了SSD算法的相關知識，如下：SSD目標檢測算法必須知道的幾個關鍵點目標檢測算法SSD結構詳解❞
  • 【SDCC 2015現場】算法實踐論壇(上):網易、京東、騰訊的算法優化...
    現場詳解如何通過基於搜索用戶日誌挖掘、基於Query短語權重的相似性糾錯等Query優化手段實現RPM上升，「精確」召回更多廣告，提升單次點擊價格。 圖：京東商城搜索推薦部總監 劉思喆 京東推薦算法優化以數據分析為工具，提升數據的質量和覆蓋度，測試不同算法在不同數據源的效果，提高召回模型的質量
  • 數據結構與算法之拓撲排序
    前言今天忽然想起了去年華為軟挑的題目，與圖論有關，其中也涉及到了一部分拓撲排序的知識，然後本來想寫一些BFS和DFS
  • 密碼學_RSA算法原理詳解
    RSA算法基於一個非常簡單的數論事實：兩個素數相乘得到一個大數很容易，但是由一個大數分解為兩個素數相乘卻非常難。RSA公鑰加密算法是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。1987年首次公布，當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。
  • 二分圖的最大匹配、完美匹配和匈牙利算法
    匈牙利算法是基於Hall定理中充分性證明的思想，它是二部圖匹配最常見的算法，該算法的核心就是尋找增廣路徑，它是一種用增廣路徑求二分圖最大匹配的算法。這篇文章講無權二分圖（unweighted bipartite graph）的最大匹配（maximum matching）和完美匹配（perfect matching），以及用於求解匹配的匈牙利算法（Hungarian Algorithm）；不講帶權二分圖的最佳匹配。