讀完本文，你可以去力扣拿下如下題目：
111.二叉樹的最小深度
752.開啟轉盤鎖
-----------
後臺有很多人問起 BFS 和 DFS 的框架，今天就來說說吧。
BFS 的核心思想應該不難理解的，就是把一些問題抽象成圖，從一個點開始，向四周開始擴散。一般來說，我們寫 BFS 演算法都是用「佇列」這種資料結構，每次將一個節點周圍的所有節點加入佇列。
BFS 相對 DFS 的最主要的區別是：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(); /* 將當前佇列中的所有節點向四周擴散 */ for (int i = 0; i < sz; i++) { Node cur = q.poll(); /* 劃重點：這裡判斷是否到達終點 */ if (cur is target) return step; /* 將 cur 的相鄰節點加入佇列 */ for (Node x : cur.adj()) if (x not in visited) { q.offer(x); visited.add(x); } } /* 劃重點：更新步數在這裡 */ step++; }}佇列 q 就不說了，BFS 的核心資料結構；cur.adj() 泛指 cur 相鄰的節點，比如說二維陣列中，cur 上下左右四面的位置就是相鄰節點；visited 的主要作用是防止走回頭路，大部分時候都是必須的，但是像一般的二叉樹結構，沒有子節點到父節點的指標，不會走回頭路就不需要 visited。
二、二叉樹的最小高度先來個簡單的問題實踐一下 BFS 框架吧，判斷一棵二叉樹的最小高度，這也是 LeetCode 第 111 題，看一下題目：
怎麼套到 BFS 的框架裡呢？首先明確一下起點 start 和終點 target 是什麼，怎麼判斷到達了終點？
顯然起點就是 root 根節點，終點就是最靠近根節點的那個「葉子節點」嘛，葉子節點就是兩個子節點都是 null 的節點：
if (cur.left == null && cur.right == null) // 到達葉子節點那麼，按照我們上述的框架稍加改造來寫解法即可：
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(); /* 將當前佇列中的所有節點向四周擴散 */ for (int i = 0; i < sz; i++) { TreeNode cur = q.poll(); /* 判斷是否到達終點 */ if (cur.left == null && cur.right == null) return depth; /* 將 cur 的相鄰節點加入佇列 */ if (cur.left != null) q.offer(cur.left); if (cur.right != null) q.offer(cur.right); } /* 這裡增加步數 */ depth++; } return depth;}二叉樹是很簡單的資料結構，我想上述程式碼你應該可以理解的吧，其實其他複雜問題都是這個框架的變形，再探討複雜問題之前，我們解答兩個問題：
1、為什麼 BFS 可以找到最短距離，DFS 不行嗎？
首先，你看 BFS 的邏輯，depth 每增加一次，佇列中的所有節點都向前邁一步，這保證了第一次到達終點的時候，走的步數是最少的。
DFS 不能找最短路徑嗎？其實也是可以的，但是時間複雜度相對高很多。你想啊，DFS 實際上是靠遞迴的堆疊記錄走過的路徑，你要找到最短路徑，肯定得把二叉樹中所有樹杈都探索完才能對比出最短的路徑有多長對不對？而 BFS 藉助佇列做到一次一步「齊頭並進」，是可以在不遍歷完整棵樹的條件下找到最短距離的。
形象點說，DFS 是線，BFS 是面；DFS 是單打獨鬥，BFS 是集體行動。這個應該比較容易理解吧。
2、既然 BFS 那麼好，為啥 DFS 還要存在？
BFS 可以找到最短距離，但是空間複雜度高，而 DFS 的空間複雜度較低。
還是拿剛才我們處理二叉樹問題的例子，假設給你的這個二叉樹是滿二叉樹，節點數為 N，對於 DFS 演算法來說，空間複雜度無非就是遞迴堆疊，最壞情況下頂多就是樹的高度，也就是 O(logN)。
但是你想想 BFS 演算法，佇列中每次都會儲存著二叉樹一層的節點，這樣的話最壞情況下空間複雜度應該是樹的最底層節點的數量，也就是 N/2，用 Big O 表示的話也就是 O(N)。
由此觀之，BFS 還是有代價的，一般來說在找最短路徑的時候使用 BFS，其他時候還是 DFS 使用得多一些（主要是遞迴程式碼好寫）。
好了，現在你對 BFS 瞭解得足夠多了，下面來一道難一點的題目，深化一下框架的理解吧。
三、解開密碼鎖的最少次數這道 LeetCode 題目是第 752 題，比較有意思：
題目中描述的就是我們生活中常見的那種密碼鎖，若果沒有任何約束，最少的撥動次數很好算，就像我們平時開密碼鎖那樣直奔密碼撥就行了。
但現在的難點就在於，不能出現 deadends，應該如何計算出最少的轉動次數呢？
第一步，我們不管所有的限制條件，不管 deadends 和 target 的限制，就思考一個問題：如果讓你設計一個演算法，窮舉所有可能的密碼組合，你怎麼做？
窮舉唄，再簡單一點，如果你只轉一下鎖，有幾種可能？總共有 4 個位置，每個位置可以向上轉，也可以向下轉，也就是有 8 種可能對吧。
比如說從 "0000" 開始，轉一次，可以窮舉出 "1000", "9000", "0100", "0900"... 共 8 種密碼。然後，再以這 8 種密碼作為基礎，對每個密碼再轉一下，窮舉出所有可能...
仔細想想，這就可以抽象成一幅圖，每個節點有 8 個相鄰的節點，又讓你求最短距離，這不就是典型的 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(); /* 將當前佇列中的所有節點向周圍擴散 */ for (int i = 0; i < sz; i++) { String cur = q.poll(); /* 判斷是否到達終點 */ System.out.println(cur); /* 將一個節點的相鄰節點加入佇列 */ 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"，這樣的話會產生死迴圈。
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<>(); // 從起點開始啟動廣度優先搜尋 int step = 0; q.offer("0000"); visited.add("0000"); while (!q.isEmpty()) { int sz = q.size(); /* 將當前佇列中的所有節點向周圍擴散 */ for (int i = 0; i < sz; i++) { String cur = q.poll(); /* 判斷是否到達終點 */ if (deads.contains(cur)) continue; if (cur.equals(target)) return step; /* 將一個節點的未遍歷相鄰節點加入佇列 */ 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;}至此，我們就解決這道題目了。有一個比較小的最佳化：可以不需要 dead 這個雜湊集合，可以直接將這些元素初始化到 visited 集合中，效果是一樣的，可能更加優雅一些。
四、雙向 BFS 最佳化你以為到這裡 BFS 演算法就結束了？恰恰相反。BFS 演算法還有一種稍微高階一點的最佳化思路：雙向 BFS，可以進一步提高演算法的效率。
篇幅所限，這裡就提一下區別：傳統的 BFS 框架就是從起點開始向四周擴散，遇到終點時停止；而雙向 BFS 則是從起點和終點同時開始擴散，當兩邊有交集的時候停止。
為什麼這樣能夠能夠提升效率呢？其實從 Big O 表示法分析演算法複雜度的話，它倆的最壞複雜度都是 O(N)，但是實際上雙向 BFS 確實會快一些，我給你畫兩張圖看一眼就明白了：
圖示中的樹形結構，如果終點在最底部，按照傳統 BFS 演算法的策略，會把整棵樹的節點都搜尋一遍，最後找到 target；而雙向 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 中的所有節點向周圍擴散 */ for (String cur : q1) { /* 判斷是否到達終點 */ if (deads.contains(cur)) continue; if (q2.contains(cur)) return step; visited.add(cur); /* 將一個節點的未遍歷相鄰節點加入集合 */ 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 迴圈的最後交換 q1 和 q2 的內容，所以只要預設擴散 q1 就相當於輪流擴散 q1 和 q2。
其實雙向 BFS 還有一個最佳化，就是在 while 迴圈開始時做一個判斷：
// ...while (!q1.isEmpty() && !q2.isEmpty()) { if (q1.size() > q2.size()) { // 交換 q1 和 q2 temp = q1; q1 = q2; q2 = temp; } // ...為什麼這是一個最佳化呢？
因為按照 BFS 的邏輯，佇列（集合）中的元素越多，擴散之後新的佇列（集合）中的元素就越多；在雙向 BFS 演算法中，如果我們每次都選擇一個較小的集合進行擴散，那麼佔用的空間增長速度就會慢一些，效率就會高一些。
不過話說回來，無論傳統 BFS 還是雙向 BFS，無論做不做最佳化，從 Big O 衡量標準來看，時間複雜度都是一樣的，只能說雙向 BFS 是一種 trick，演算法執行的速度會相對快一點，掌握不掌握其實都無所謂。最關鍵的是把 BFS 通用框架記下來，反正所有 BFS 演算法都可以用它套出解法。