共计 6553 个字符，预计需要花费 17 分钟才能阅读完成。
读完本文，你能够去力扣拿下如下题目：
111. 二叉树的最小深度
752. 关上转盘锁
———–
后盾有很多人问起 BFS 和 DFS 的框架，明天就来说说吧。
首先，你要说 labuladong 没写过 BFS 框架，这话没错，明天写个框架你背住就完事儿了。但要是说没写过 DFS 框架，那你还真是说错了，其实 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 高效的。
不过，双向 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 算法都能够用它套出解法。
