讀完本文，你可以去力扣拿下如下題目：

111.二叉樹的最小深度

752.打開轉盤鎖

-----------

后臺有很多人問起 BFS 和 DFS 的框架芬迄，今天就來說說吧问顷。

首先，你要說 labuladong 沒寫過 BFS 框架，這話沒錯杜窄，今天寫個框架你背住就完事兒了肠骆。但要是說沒寫過 DFS 框架，那你還真是說錯了羞芍，其實 DFS 算法就是回溯算法，我們前文 回溯算法框架套路詳解 就寫過了郊艘，而且寫得不是一般得好荷科，建議好好復習。

BFS 的核心思想應該不難理解的纱注，就是把一些問題抽象成圖畏浆，從一個點開始，向四周開始擴散狞贱。一般來說刻获，我們寫 BFS 算法都是用「隊列」這種數據結構，每次將一個節(jié)點周圍的所有節(jié)點加入隊列瞎嬉。

BFS 相對 DFS 的最主要的區(qū)別是：BFS 找到的路徑一定是最短的蝎毡，但代價就是空間復雜度比 DFS 大很多，至于為什么氧枣，我們后面介紹了框架就很容易看出來了沐兵。

本文就由淺入深寫兩道 BFS 的典型題目，分別是「二叉樹的最小高度」和「打開密碼鎖的最少步數」便监，手把手教你怎么寫 BFS 算法扎谎。

一、算法框架

要說框架的話烧董，我們先舉例一下 BFS 出現的常見場景好吧毁靶，問題的本質就是讓你在一幅「圖」中找到從起點 start 到終點 target 的最近距離，這個例子聽起來很枯燥逊移，但是 BFS 算法問題其實都是在干這個事兒预吆，把枯燥的本質搞清楚了，再去欣賞各種問題的包裝才能胸有成竹嘛胳泉。

這個廣義的描述可以有各種變體啡浊，比如走迷宮，有的格子是圍墻不能走胶背，從起點到終點的最短距離是多少巷嚣？如果這個迷宮帶「傳送門」可以瞬間傳送呢？

再比如說兩個單詞钳吟，要求你通過某些替換廷粒，把其中一個變成另一個，每次只能替換一個字符，最少要替換幾次坝茎？

再比如說連連看游戲涤姊，兩個方塊消除的條件不僅僅是圖案相同，還得保證兩個方塊之間的最短連線不能多于兩個拐點嗤放。你玩連連看思喊，點擊兩個坐標，游戲是如何判斷它倆的最短連線有幾個拐點的次酌？

再比如……

凈整些花里胡哨的恨课，這些問題都沒啥奇技淫巧，本質上就是一幅「圖」岳服，讓你從一個起點剂公，走到終點窘奏，問最短路徑括细。這就是 BFS 的本質莺奔，框架搞清楚了直接默寫就好淮捆。

記住下面這個框架就 OK 了：

// 計算從起點 start 到終點 target 的最近距離
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心數據結構
    Set<Node> visited; // 避免走回頭路
    
    q.offer(start); // 將起點加入隊列
    visited.add(start);
    int step = 0; // 記錄擴散的步數

    while (q not empty) {
        int sz = q.size();
        /* 將當前隊列中的所有節(jié)點向四周擴散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 劃重點：這里判斷是否到達終點 */
            if (cur is target)
                return step;
            /* 將 cur 的相鄰節(jié)點加入隊列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 劃重點：更新步數在這里 */
        step++;
    }
}

隊列 q 就不說了继低，BFS 的核心數據結構叼耙；cur.adj() 泛指 cur 相鄰的節(jié)點鼻疮，比如說二維數組中琳水，cur 上下左右四面的位置就是相鄰節(jié)點这吻；visited 的主要作用是防止走回頭路绿贞，大部分時候都是必須的，但是像一般的二叉樹結構橘原，沒有子節(jié)點到父節(jié)點的指針籍铁，不會走回頭路就不需要 visited。

二趾断、二叉樹的最小高度

先來個簡單的問題實踐一下 BFS 框架吧拒名，判斷一棵二叉樹的最小高度，這也是 LeetCode 第 111 題芋酌，看一下題目：

image

怎么套到 BFS 的框架里呢增显？首先明確一下起點 start 和終點 target 是什么，怎么判斷到達了終點脐帝？

顯然起點就是 root 根節(jié)點同云，終點就是最靠近根節(jié)點的那個「葉子節(jié)點」嘛，葉子節(jié)點就是兩個子節(jié)點都是 null 的節(jié)點：

if (cur.left == null && cur.right == null) 
    // 到達葉子節(jié)點

那么堵腹，按照我們上述的框架稍加改造來寫解法即可：

int minDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    // root 本身就是一層炸站，depth 初始化為 1
    int depth = 1;
    
    while (!q.isEmpty()) {
        int sz = q.size();
        /* 將當前隊列中的所有節(jié)點向四周擴散 */
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            /* 判斷是否到達終點 */
            if (cur.left == null && cur.right == null) 
                return depth;
            /* 將 cur 的相鄰節(jié)點加入隊列 */
            if (cur.left != null)
                q.offer(cur.left);
            if (cur.right != null) 
                q.offer(cur.right);
        }
        /* 這里增加步數 */
        depth++;
    }
    return depth;
}

二叉樹是很簡單的數據結構，我想上述代碼你應該可以理解的吧疚顷，其實其他復雜問題都是這個框架的變形旱易，再探討復雜問題之前禁偎，我們解答兩個問題：

1、為什么 BFS 可以找到最短距離阀坏，DFS 不行嗎如暖？

首先，你看 BFS 的邏輯忌堂，depth 每增加一次盒至，隊列中的所有節(jié)點都向前邁一步，這保證了第一次到達終點的時候士修，走的步數是最少的枷遂。

DFS 不能找最短路徑嗎？其實也是可以的李命，但是時間復雜度相對高很多登淘。你想啊箫老，DFS 實際上是靠遞歸的堆棧記錄走過的路徑封字，你要找到最短路徑，肯定得把二叉樹中所有樹杈都探索完才能對比出最短的路徑有多長對不對耍鬓？而 BFS 借助隊列做到一次一步「齊頭并進」阔籽，是可以在不遍歷完整棵樹的條件下找到最短距離的。

形象點說牲蜀，DFS 是線笆制，BFS 是面；DFS 是單打獨斗涣达，BFS 是集體行動在辆。這個應該比較容易理解吧。

2度苔、既然 BFS 那么好匆篓，為啥 DFS 還要存在？

BFS 可以找到最短距離寇窑，但是空間復雜度高鸦概，而 DFS 的空間復雜度較低。

還是拿剛才我們處理二叉樹問題的例子甩骏，假設給你的這個二叉樹是滿二叉樹窗市，節(jié)點數為 N，對于 DFS 算法來說饮笛，空間復雜度無非就是遞歸堆棧咨察，最壞情況下頂多就是樹的高度，也就是 O(logN)福青。

但是你想想 BFS 算法扎拣，隊列中每次都會儲存著二叉樹一層的節(jié)點，這樣的話最壞情況下空間復雜度應該是樹的最底層節(jié)點的數量，也就是 N/2二蓝，用 Big O 表示的話也就是 O(N)誉券。

由此觀之，BFS 還是有代價的刊愚，一般來說在找最短路徑的時候使用 BFS踊跟，其他時候還是 DFS 使用得多一些（主要是遞歸代碼好寫）。

好了鸥诽，現在你對 BFS 了解得足夠多了商玫，下面來一道難一點的題目，深化一下框架的理解吧牡借。

三拳昌、解開密碼鎖的最少次數

這道 LeetCode 題目是第 752 題，比較有意思：

image

題目中描述的就是我們生活中常見的那種密碼鎖钠龙，若果沒有任何約束炬藤，最少的撥動次數很好算，就像我們平時開密碼鎖那樣直奔密碼撥就行了碴里。

但現在的難點就在于沈矿，不能出現 deadends，應該如何計算出最少的轉動次數呢咬腋？

第一步羹膳，我們不管所有的限制條件，不管 deadends 和 target 的限制根竿，就思考一個問題：如果讓你設計一個算法陵像，窮舉所有可能的密碼組合，你怎么做寇壳？

窮舉唄醒颖，再簡單一點，如果你只轉一下鎖九巡，有幾種可能图贸？總共有 4 個位置，每個位置可以向上轉冕广，也可以向下轉疏日，也就是有 8 種可能對吧。

比如說從 "0000" 開始撒汉，轉一次沟优，可以窮舉出 "1000", "9000", "0100", "0900"... 共 8 種密碼。然后睬辐，再以這 8 種密碼作為基礎挠阁，對每個密碼再轉一下宾肺，窮舉出所有可能...

仔細想想，這就可以抽象成一幅圖侵俗，每個節(jié)點有 8 個相鄰的節(jié)點锨用，又讓你求最短距離，這不就是典型的 BFS 嘛隘谣，框架就可以派上用場了增拥，先寫出一個「簡陋」的 BFS 框架代碼再說別的：

// 將 s[j] 向上撥動一次
String plusOne(String s, int j) {
    char[] ch = s.toCharArray();
    if (ch[j] == '9')
        ch[j] = '0';
    else
        ch[j] += 1;
    return new String(ch);
}
// 將 s[i] 向下撥動一次
String minusOne(String s, int j) {
    char[] ch = s.toCharArray();
    if (ch[j] == '0')
        ch[j] = '9';
    else
        ch[j] -= 1;
    return new String(ch);
}

// BFS 框架，打印出所有可能的密碼
void BFS(String target) {
    Queue<String> q = new LinkedList<>();
    q.offer("0000");
    
    while (!q.isEmpty()) {
        int sz = q.size();
        /* 將當前隊列中的所有節(jié)點向周圍擴散 */
        for (int i = 0; i < sz; i++) {
            String cur = q.poll();
            /* 判斷是否到達終點 */
            System.out.println(cur);

            /* 將一個節(jié)點的相鄰節(jié)點加入隊列 */
            for (int j = 0; j < 4; j++) {
                String up = plusOne(cur, j);
                String down = minusOne(cur, j);
                q.offer(up);
                q.offer(down);
            }
        }
        /* 在這里增加步數 */
    }
    return;
}

PS：這段代碼當然有很多問題寻歧，但是我們做算法題肯定不是一蹴而就的掌栅，而是從簡陋到完美的。不要完美主義码泛，咱要慢慢來猾封，好不。

這段 BFS 代碼已經能夠窮舉所有可能的密碼組合了噪珊，但是顯然不能完成題目晌缘，有如下問題需要解決：

1、會走回頭路卿城。比如說我們從 "0000" 撥到 "1000"枚钓，但是等從隊列拿出 "1000" 時铅搓，還會撥出一個 "0000"瑟押，這樣的話會產生死循環(huán)。

2星掰、沒有終止條件多望，按照題目要求，我們找到 target 就應該結束并返回撥動的次數氢烘。

3怀偷、沒有對 deadends 的處理，按道理這些「死亡密碼」是不能出現的播玖，也就是說你遇到這些密碼的時候需要跳過椎工。

如果你能夠看懂上面那段代碼，真得給你鼓掌蜀踏，只要按照 BFS 框架在對應的位置稍作修改即可修復這些問題：

int openLock(String[] deadends, String target) {
    // 記錄需要跳過的死亡密碼
    Set<String> deads = new HashSet<>();
    for (String s : deadends) deads.add(s);
    // 記錄已經窮舉過的密碼维蒙，防止走回頭路
    Set<String> visited = new HashSet<>();
    Queue<String> q = new LinkedList<>();
    // 從起點開始啟動廣度優(yōu)先搜索
    int step = 0;
    q.offer("0000");
    visited.add("0000");
    
    while (!q.isEmpty()) {
        int sz = q.size();
        /* 將當前隊列中的所有節(jié)點向周圍擴散 */
        for (int i = 0; i < sz; i++) {
            String cur = q.poll();
            
            /* 判斷是否到達終點 */
            if (deads.contains(cur))
                continue;
            if (cur.equals(target))
                return step;
            
            /* 將一個節(jié)點的未遍歷相鄰節(jié)點加入隊列 */
            for (int j = 0; j < 4; j++) {
                String up = plusOne(cur, j);
                if (!visited.contains(up)) {
                    q.offer(up);
                    visited.add(up);
                }
                String down = minusOne(cur, j);
                if (!visited.contains(down)) {
                    q.offer(down);
                    visited.add(down);
                }
            }
        }
        /* 在這里增加步數 */
        step++;
    }
    // 如果窮舉完都沒找到目標密碼，那就是找不到了
    return -1;
}

至此果覆，我們就解決這道題目了颅痊。有一個比較小的優(yōu)化：可以不需要 dead 這個哈希集合，可以直接將這些元素初始化到 visited 集合中局待，效果是一樣的斑响，可能更加優(yōu)雅一些菱属。

四、雙向 BFS 優(yōu)化

你以為到這里 BFS 算法就結束了舰罚？恰恰相反纽门。BFS 算法還有一種稍微高級一點的優(yōu)化思路：雙向 BFS，可以進一步提高算法的效率营罢。

篇幅所限膜毁，這里就提一下區(qū)別：傳統(tǒng)的 BFS 框架就是從起點開始向四周擴散，遇到終點時停止愤钾；而雙向 BFS 則是從起點和終點同時開始擴散瘟滨，當兩邊有交集的時候停止。

為什么這樣能夠能夠提升效率呢能颁？其實從 Big O 表示法分析算法復雜度的話杂瘸，它倆的最壞復雜度都是 O(N)，但是實際上雙向 BFS 確實會快一些伙菊，我給你畫兩張圖看一眼就明白了：

image

image

圖示中的樹形結構败玉，如果終點在最底部，按照傳統(tǒng) BFS 算法的策略镜硕，會把整棵樹的節(jié)點都搜索一遍运翼，最后找到 target；而雙向 BFS 其實只遍歷了半棵樹就出現了交集兴枯，也就是找到了最短距離血淌。從這個例子可以直觀地感受到，雙向 BFS 是要比傳統(tǒng) BFS 高效的财剖。

不過悠夯，雙向 BFS 也有局限，因為你必須知道終點在哪里躺坟。比如我們剛才討論的二叉樹最小高度的問題沦补，你一開始根本就不知道終點在哪里，也就無法使用雙向 BFS咪橙；但是第二個密碼鎖的問題夕膀，是可以使用雙向 BFS 算法來提高效率的，代碼稍加修改即可：

int openLock(String[] deadends, String target) {
    Set<String> deads = new HashSet<>();
    for (String s : deadends) deads.add(s);
    // 用集合不用隊列美侦，可以快速判斷元素是否存在
    Set<String> q1 = new HashSet<>();
    Set<String> q2 = new HashSet<>();
    Set<String> visited = new HashSet<>();
    
    int step = 0;
    q1.add("0000");
    q2.add(target);
    
    while (!q1.isEmpty() && !q2.isEmpty()) {
        // 哈希集合在遍歷的過程中不能修改产舞，用 temp 存儲擴散結果
        Set<String> temp = new HashSet<>();

        /* 將 q1 中的所有節(jié)點向周圍擴散 */
        for (String cur : q1) {
            /* 判斷是否到達終點 */
            if (deads.contains(cur))
                continue;
            if (q2.contains(cur))
                return step;
            visited.add(cur);

            /* 將一個節(jié)點的未遍歷相鄰節(jié)點加入集合 */
            for (int j = 0; j < 4; j++) {
                String up = plusOne(cur, j);
                if (!visited.contains(up))
                    temp.add(up);
                String down = minusOne(cur, j);
                if (!visited.contains(down))
                    temp.add(down);
            }
        }
        /* 在這里增加步數 */
        step++;
        // temp 相當于 q1
        // 這里交換 q1 q2，下一輪 while 就是擴散 q2
        q1 = q2;
        q2 = temp;
    }
    return -1;
}

雙向 BFS 還是遵循 BFS 算法框架的音榜，只是不再使用隊列庞瘸，而是使用 HashSet 方便快速判斷兩個集合是否有交集。

另外的一個技巧點就是 while 循環(huán)的最后交換 q1 和 q2 的內容赠叼，所以只要默認擴散 q1 就相當于輪流擴散 q1 和 q2擦囊。

其實雙向 BFS 還有一個優(yōu)化违霞，就是在 while 循環(huán)開始時做一個判斷：

// ...
while (!q1.isEmpty() && !q2.isEmpty()) {
    if (q1.size() > q2.size()) {
        // 交換 q1 和 q2
        temp = q1;
        q1 = q2;
        q2 = temp;
    }
    // ...

為什么這是一個優(yōu)化呢？

因為按照 BFS 的邏輯瞬场，隊列（集合）中的元素越多买鸽，擴散之后新的隊列（集合）中的元素就越多；在雙向 BFS 算法中贯被，如果我們每次都選擇一個較小的集合進行擴散眼五，那么占用的空間增長速度就會慢一些，效率就會高一些彤灶。

不過話說回來看幼，無論傳統(tǒng) BFS 還是雙向 BFS，無論做不做優(yōu)化幌陕，從 Big O 衡量標準來看诵姜，時間復雜度都是一樣的，只能說雙向 BFS 是一種 trick搏熄，算法運行的速度會相對快一點棚唆，掌握不掌握其實都無所謂。最關鍵的是把 BFS 通用框架記下來心例，反正所有 BFS 算法都可以用它套出解法宵凌。

＿＿＿＿＿＿＿＿＿＿＿＿＿

我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目止后，建議收藏瞎惫！對應的 GitHub 算法倉庫 已經獲得了 70k star，歡迎標星坯门！