大家好，我是讯享网，很高兴认识大家。



 <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg> <blockquote> 

讯享网

深度优先搜索和广度优先搜索是两种最常见的优先搜索方法，他们被广泛地应用在图和树等数据结构中进行搜索。

回溯算法就是一个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作。【更具体的见第二部分】

带着问题阅读 并 解决自身疑惑：

BFS出现的问题：

BFS实际应用解决的问题：① 最短路径or step or depth
②对应防止死循环，1)要有辅助结构：queue ； 2) 要有 辅助函数：邻域的的节点要能访问到 且 不至于死循环【除却 二叉树外，因为不会访问到父节点；其它的：数组啊， string啊 都要防止死循环】
③ 注意：邻域的 选取方式——对应的 要设置为 visited；且 未访问过等。
④ 注意：结束条件

回溯思想中需要注意的几个点：

废话不多说，直接上回溯算法框架。解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考4个问题：

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。 —— 【决定了搜索空间，决定了搜索空间有哪些节点。】

3、结束条件：也就是到达决策树底层，无法再做选择的条件。——【决定了什么时候捕获有效的解，提前结束递归，开始回溯。】

4、约束，用来剪枝，避免进入无效的分支。

BFS框架中需要注意的几个点：

1. visited——防止死循环，跟随 在入队时候 【邻接矩阵 visited，可以用 设置为0/2 防止不访问。】
2. do visit —— 两种方式，但是注意 根据实际情况使用。且注意 第一种位置，在两边都需要visit
3. 结束条件——如果求最短距离，注意 结束条件的变换。
4. 邻域 与 do visit 灵活运用【return 提前快速 - 参考链接T934.】

区别于BFS，深度优先搜索类似于 树的先序遍历。

题目1 最大岛屿面积

讯享网
1）解法一：简单的深度优先搜索

类似于树的先序遍历

此题是十分标准的搜索题，我们可以拿来练手深度优先搜索。一般来说，深度优先搜索类型的题可以分为主函数和辅函数，主函数用于遍历所有的搜索位置，判断是否可以开始搜索，如果可以即在辅函数进行搜索。辅函数则负责深度优先搜索的递归调用。当然，我们也可以使用栈（stack）实现深度优先搜索，但因为栈与递归的调用原理相同，而递归相对便于实现，因此刷题时笔者推荐使用递归式写法，同时也方便进行回溯（见下节） 。不过在实际工程上，直接使用栈可能才是最好的选择，一是因为便于理解，二是更不易出现递归栈满的情况。我们先展示使用栈的写法。

讯享网

2）解法二：深搜+栈形式

我们可以用栈来实现深度优先搜索算法。这种方法本质与方法一相同，唯一的区别是：

• 方法一通过函数的调用来表示接下来想要遍历哪些土地，让下一层函数来访问这些土地。而方法二把接下来想要遍历的土地放在栈里，然后在取出这些土地的时候访问它们。
• 访问每一片土地时，我们将对围绕它四个方向进行探索，找到还未访问的土地，加入到栈 stack 中；
• 另外，只要栈 stack 不为空，就说明我们还有土地待访问，那么就从栈中取出一个元素并访问。

3）解法三：广度优先搜索
我们把方法二中的栈改为队列，每次从队首取出土地，并将接下来想要遍历的土地放在队尾，就实现了广度优先搜索算法

讯享网

题目2 朋友圈

参考1 官方多种方法。
参考2 并查集。

同样有三种解法：深搜、广搜、并查集。

1. 解法一：深搜
   给定的矩阵可以看成图的邻接矩阵。这样我们的问题可以变成无向图连通块的个数。为了方便理解，考虑如下矩阵：

如果我们把 M 看成图的邻接矩阵，则图为：

在这个图中，点的编号表示矩阵 M 的下标，i和 j 之间有一条边当且仅当 为 1。

为了找到连通块的个数，一个简单的方法就是使用深度优先搜索，从每个节点开始，我们使用一个大小为 N的 visited 数组（M大小为 N×N），这样 表示第 i 个元素是否被深度优先搜索访问过。

我们首先选择一个节点，访问任一相邻的节点。然后再访问这一节点的任一相邻节点。这样不断遍历到没有未访问的相邻节点时，回溯到之前的节点进行访问。

即两个关键：①考虑实际意义，每个人 看做个体做。②看做邻接矩阵，找到置位 即可【因为深搜，用户邻接 所有的相关邻接的圈子 都会被访问完了，不用再考虑用户了】。

讯享网

2. 解法二：广搜
3. 解法三：并查集

题目3 太平洋大西洋水流问题

解法一： DFS逆流而上的大佬思维

【BFS待看待删除本句话】解法二：同上面的思维但是使用BFS进行 —— 队列按层次扩展流动

讯享网

2.0.1 读懂递归、回溯、DFS、DP(动态规划)区别与联系

1)递归是一种 算法结构，就是自我调用，经常作为一种编程的实现方式，比如题主问题中的DFS 、动态规划、回溯法都可以用递归来实现，当然也可以用非递归来实现。很多时候一个概念也可以用递归的方式来定义（比如gnu）。

递归是一种算法结构，递归会出现在子程序中自己调用自己或间接地自己调用自己。最直接的递归应用就是计算连续数的阶乘，计算规律：n!=(n-1)!*n。
观察阶乘计算的规律，前一个数结成的结果可以直接被应用到后一个数结成的计算中。

2)回溯是一种通用的算法，算法思想，把问题分步解决，在每一步都试验所有的可能，当发现已经找到一种方式或者目前这种方式不可能是结果的时候，退回上一步继续尝试其他可能。很多时候每一步的处理都是一致的，这时候用递归来实现就很自然。

回溯是一种 算法思想，可以用递归实现。通俗点讲回溯就是一种试探，类似于穷举，但回溯有“剪枝”功能，比如求和问题。给定7个数字，1 2 3 4 5 6 7求和等于7的组合，从小到大搜索，选择1+2+3+4 =10>7，已经超过了7，之后的5 6 7就没必要在继续了，这就是一种搜索过程的优化。如果还有不清楚的可以看一下8皇后问题。

3)当*回溯用于树的时候，就是深度优先搜索。*当然了，几乎所有可以用回溯解决的问题都可以表示为树。那么这俩在这里就几乎同义了。如果一个问题解决的时候显式地使用了树，那么我们就叫它dfs。很多时候没有用树我们也管它叫dfs严格地说是不对的，但是dfs比回溯打字的时候好输入。别的回答里提到了剪枝，实际上这二者都可以剪枝。

关于树：对于某一个搜索树来说（搜索树是起记录路径和状态判断的作用），回溯和DFS，其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。

而为了减少存储空间，在深度优先搜索中，用标志的方法记录访问过的状态，这种处理方法使得深度优先搜索法与回溯法没什么区别了。

4)至于动态规划，被题主放到这里是因为都是竞赛中经常会遇到并且学起来不容易明白吗？回溯可以用于所有用穷举法可以解决的问题，而DP只用于具有最优子结构的问题。所以不是所有问题都适合用dp来解决，比如八皇后。dp需要存贮子问题的解，回溯不需要。

2.0.2 正文思维框架

这篇文章是很久之前的一篇《回溯算法详解》的进阶版，之前那篇不够清楚，就不必看了，看这篇就行。把框架给你讲清楚，你会发现回溯算法问题都是一个套路。

废话不多说，直接上回溯算法框架。解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考4个问题：

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。 —— 【决定了搜索空间，决定了搜索空间有哪些节点。】

3、结束条件：也就是到达决策树底层，无法再做选择的条件。——【决定了什么时候捕获有效的解，提前结束递归，开始回溯。】

4、约束，用来剪枝，避免进入无效的分支。

如果你不理解这三个词语的解释，没关系，我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思，现在你先留着印象。

代码方面，回溯算法的框架：

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。

什么叫做选择和撤销选择呢，这个框架的底层原理是什么呢？下面我们就通过「全排列」这个问题来解开之前的疑惑，详细探究一下其中的奥妙！

2.1 全排列问题

我们在高中的时候就做过排列组合的数学题，我们也知道n个不重复的数，全排列共有 n! 个。

PS：为了简单清晰起见，我们这次讨论的全排列问题不包含重复的数字。

那么我们当时是怎么穷举全排列的呢？比方说给三个数[1,2,3]，你肯定不会无规律地乱穷举，一般是这样：

先固定第一位为 1，然后第二位可以是 2，那么第三位只能是 3；然后可以把第二位变成 3，第三位就只能是 2 了；然后就只能变化第一位，变成 2，然后再穷举后两位……

其实这就是回溯算法，我们高中无师自通就会用，或者有的同学直接画出如下这棵回溯树：

只要从根遍历这棵树，记录路径上的数字，其实就是所有的全排列。我们不妨把这棵树称为回溯算法的「决策树」。

为啥说这是决策树呢，因为你在每个节点上其实都在做决策。比如说你站在下图的红色节点上：

你现在就在做决策，可以选择 1 那条树枝，也可以选择 3 那条树枝。为啥只能在 1 和 3 之中选择呢？因为 2 这个树枝在你身后，这个选择你之前做过了，而全排列是不允许重复使用数字的。

现在可以解答开头的几个名词：[2]就是「路径」，记录你已经做过的选择；[1,3]就是「选择列表」，表示你当前可以做出的选择；「结束条件」就是遍历到树的底层，在这里就是选择列表为空的时候。

如果明白了这几个名词，可以把「路径」和「选择列表」作为决策树上每个节点的属性，比如下图列出了几个节点的属性：

我们定义的backtrack函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个全排列。

再进一步，如何遍历一棵树？这个应该不难吧。回忆一下之前 学习数据结构的框架思维 写过，各种搜索问题其实都是树的遍历问题，而多叉树的遍历框架就是这样：

讯享网

而所谓的前序遍历和后序遍历，他们只是两个很有用的时间点，我给你画张图你就明白了：

前序遍历的代码在进入某一个节点之前的那个时间点执行，后序遍历代码在离开某个节点之后的那个时间点执行。

回想我们刚才说的，「路径」和「选择」是每个节点的属性，函数在树上游走要正确维护节点的属性，那么就要在这两个特殊时间点搞点动作：

现在，你是否理解了回溯算法的这段核心框架？

我们只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径。

下面，直接看全排列代码：

讯享网

我们这里稍微做了些变通，没有显式记录「选择列表」，而是通过nums和track推导出当前的选择列表：

【注意：这里对应的我的 C++解法完整版】

至此，我们就通过全排列问题详解了回溯算法的底层原理。当然，这个算法解决全排列不是很高效，因为对链表使用contains方法需要 O(N) 的时间复杂度。有更好的方法通过交换元素达到目的，但是难理解一些，这里就不写了，有兴趣可以自行搜索一下。

但是必须说明的是，不管怎么优化，都符合回溯框架，而且时间复杂度都不可能低于 O(N!)，因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

附赠 —— 组合问题求解：

讯享网

附赠 —— 单词搜索问题求解：

【关键点—回溯】：首先遍历 board 的所有元素，先找到和 word 第一个字母相同的元素，然后进入递归流程。假设这个元素的坐标为 (i, j)，进入递归流程前，先记得把该元素打上使用过的标记： visited[i][j] = true

【注意点–边界和return 检查：】
1）递归时元素的坐标是否超过边界；
2）回溯标记 mark[i][j] = 0以及 return 的时机

明白了全排列问题，就可以直接套回溯算法框架了，下面简单看看 N 皇后问题。

2.2 N 皇后问题

这个问题很经典了，简单解释一下：给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击。

PS：皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。

这是 N = 8 的一种放置方法：

图片来自 LeetCode

这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。

直接套用框架:

讯享网

这部分主要代码，跟全排列问题差不多。函数的实现也很简单：

函数backtrack依然像个在决策树上游走的指针，每个节点就表示在board[row][col]上放置皇后，通过isValid函数可以将不符合条件的情况剪枝：

如果直接给你这么一大段解法代码，可能是懵逼的。但是现在明白了回溯算法的框架套路，还有啥难理解的呢？无非是改改做选择的方式，排除不合法选择的方式而已，只要框架存于心，你面对的只剩下小问题了。

当N = 8时，就是八皇后问题，数学大佬高斯穷尽一生都没有数清楚八皇后问题到底有几种可能的放置方法，但是我们的算法只需要一秒就可以算出来所有可能的结果。

不过真的不怪高斯。这个问题的复杂度确实非常高，看看我们的决策树，虽然有isValid函数剪枝，但是最坏时间复杂度仍然是 O(N^(N+1))，而且无法优化。如果N = 10的时候，计算就已经很耗时了。

有的时候，我们并不想得到所有合法的答案，只想要一个答案，怎么办呢？比如解数独的算法，找所有解法复杂度太高，只要找到一种解法就可以。

其实特别简单，只要稍微修改一下回溯算法的代码即可：

讯享网

这样修改后，只要找到一个答案，for 循环的后续递归穷举都会被阻断。也许你可以在 N 皇后问题的代码框架上，稍加修改，写一个解数独的算法？
附加——我的解法：对比labuladong；在对角线上 使用了 做差的绝对值相等

附加——大佬101的解法——对角线更好！直接标志就好！不用以上两种的遍历啦！

以上直接找到对角线规律，主对角线：ldiag(2n-1, false), 副对角线： rdiag(2n-1,false);
对应位置：column[i] = ldiag[row-i+n-1] = rdiag[row+i] = true; 【即可！】

讯享网

2.3 最后总结

回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作，算法框架如下：
废话不多说，直接上回溯算法框架。解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 4个问题：

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。 —— 【决定了搜索空间，决定了搜索空间有哪些节点。】

3、结束条件：也就是到达决策树底层，无法再做选择的条件。——【决定了什么时候捕获有效的解，提前结束递归，开始回溯。】

4、约束，用来剪枝，避免进入无效的分支。

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。

关键之处：回溯的三要点

1. 选择，决定了搜索空间，决定了搜索空间有哪些节点。
2. 约束，用来剪枝，避免进入无效的分支。
3. 目标，决定了什么时候捕获有效的解，提前结束递归，开始回溯。

---

写backtrack函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。

其实想想看，回溯算法和动态规划是不是有点像呢？我们在动态规划系列文章中多次强调，动态规划的三个需要明确的点就是「状态」「选择」和「base case」，是不是就对应着走过的「路径」，当前的「选择列表」和「结束条件」？

某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划。而今天的两个问题，都没有重叠子问题，也就是回溯算法问题了，复杂度非常高是不可避免的。

2.4 回溯思想的实际应用见链接

广度优先搜索是一种分层的查找过程。查找距离起点最近的点。
区别于DFS可以递归，BFS没有回退情况—— 所以需要借助辅助队列——以记忆正在访问的顶点和下一层顶点。
后台有很多人问起 BFS 和 DFS 的框架，今天就来说说吧。

首先，你要说 labuladong 没写过 BFS 框架，这话没错，今天写个框架你背住就完事儿了。但要是说没写过 DFS 框架，那你还真是说错了，其实 DFS 算法就是回溯算法，我们前文 回溯算法框架套路详解 就写过了，而且写得不是一般得好，建议好好复习。

BFS 的核心思想应该不难理解的，就是把一些问题抽象成图，从一个点开始，向四周开始扩散。一般来说，我们写 BFS 算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。

BFS 相对 DFS 的最主要的区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多，至于为什么，我们后面介绍了框架就很容易看出来了。

本文就由浅入深写两道 BFS 的典型题目，分别是「二叉树的最小高度」和「打开密码锁的最少步数」，手把手教你怎么写 BFS 算法。

BFS框架中需要注意的几个点：

1. visited——防止死循环，跟随 在入队时候
2. do visit —— 两种方式，但是注意 根据实际情况使用。且注意 第一种位置，在两边都需要visit
3. 结束条件——如果求最短距离，注意 结束条件的变换。

3.1 算法框架

要说框架的话，我们先举例一下 BFS 出现的常见场景好吧， 问题的本质就是让你在一幅「图」中找到从起点到终点的最近距离，这个例子听起来很枯燥，但是 BFS 算法问题其实都是在干这个事儿。

把枯燥的本质搞清楚了，再去欣赏各种问题的包装才能胸有成竹嘛。

这个广义的描述可以有各种变体，比如走迷宫，有的格子是围墙不能走，从起点到终点的最短距离是多少？如果这个迷宫带「传送门」可以瞬间传送呢？

再比如说两个单词，要求你通过某些替换，把其中一个变成另一个，每次只能替换一个字符，最少要替换几次？

再比如说连连看游戏，两个方块消除的条件不仅仅是图案相同，还得保证两个方块之间的最短连线不能多于两个拐点。你玩连连看，点击两个坐标，游戏是如何判断它俩的最短连线有几个拐点的？

再比如……

净整些花里胡哨的，这些问题都没啥奇技淫巧，本质上就是一幅「图」，让你从一个起点，走到终点，问最短路径。这就是 BFS 的本质，框架搞清楚了直接默写就好。

记住下面这个框架就 OK 了：

讯享网

【注意：】
队列就不说了，BFS 的核心数据结构；泛指相邻的节点，比如说二维数组中，上下左右四面的位置就是相邻节点；的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要。

3.2 二叉树的最小高度

先来个简单的问题实践一下 BFS 框架吧，判断一棵二叉树的最小高度，这也是 LeetCode 第 111 题，看一下题目：

怎么套到 BFS 的框架里呢？首先明确一下起点start和终点target是什么，怎么判断到达了终点？

显然起点就是root根节点，终点就是最靠近根节点的那个「叶子节点」嘛，叶子节点就是两个子节点都是null的节点：

那么，按照我们上述的框架稍加改造来写解法即可：

讯享网

二叉树是很简单的数据结构，我想上述代码你应该可以理解的吧，其实其他复杂问题都是这个框架的变形，在探讨复杂问题之前，我们解答两个问题：

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 了解得足够多了，下面来一道难一点的题目，深化一下框架的理解吧。

3.3 解开密码锁的最少次数

这道 LeetCode 题目是第 752 题，比较有意思：

题目中描述的就是我们生活中常见的那种密码锁，若果没有任何约束，最少的拨动次数很好算，就像我们平时开密码锁那样直奔密码拨就行了。

但现在的难点就在于，不能出现deadends，应该如何计算出最少的转动次数呢？

第一步，我们不管所有的限制条件，不管deadends和target的限制，就思考一个问题：如果让你设计一个算法，穷举所有可能的密码组合，你怎么做？

穷举呗，再简单一点，如果你只转一下锁，有几种可能？总共有 4 个位置，每个位置可以向上转，也可以向下转，也就是有 8 种可能对吧。

比如说从“0000”开始，转一次，可以穷举出“1000”, “9000”, “0100”, “0900”…共 8 种密码。然后，再以这 8 种密码作为基础，对每个密码再转一下，穷举出所有可能…

仔细想想，这就可以抽象成一幅图，每个节点有 8 个相邻的节点，又让你求最短距离，这不就是典型的 BFS 嘛，框架就可以派上用场了，先写出一个「简陋」的 BFS 框架代码再说别的：

PS：这段代码当然有很多问题，但是我们做算法题肯定不是一蹴而就的，而是从简陋到完美的。不要完美主义，咱要慢慢来，好不。

这段 BFS 代码已经能够穷举所有可能的密码组合了，但是显然不能完成题目，有如下问题需要解决：

1、会走回头路。比如说我们从“0000”拨到“1000”，但是等从队列拿出“1000”时，还会拨出一个“0000”，这样的话会产生死循环。

2、没有终止条件，按照题目要求，我们找到target就应该结束并返回拨动的次数。

3、没有对deadends的处理，按道理这些「死亡密码」是不能出现的，也就是说你遇到这些密码的时候需要跳过。

如果你能够看懂上面那段代码，真得给你鼓掌，只要按照 BFS 框架在对应的位置稍作修改即可修复这些问题：

讯享网

至此，我们就解决这道题目了。有一个比较小的优化：可以不需要dead这个哈希集合，可以直接将这些元素初始化到visited集合中，效果是一样的，可能更加优雅一些。

我的C++样式

3.4 双向 BFS 优化

你以为到这里 BFS 算法就结束了？恰恰相反。BFS 算法还有一种稍微高级一点的优化思路：双向 BFS，可以进一步提高算法的效率。

篇幅所限，这里就提一下区别：传统的 BFS 框架就是从起点开始向四周扩散，遇到终点时停止；而双向 BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停止。

为什么这样能够能够提升效率呢？其实从 Big O 表示法分析算法复杂度的话，它俩的最坏复杂度都是O(N)，但是实际上双向 BFS 确实会快一些，我给你画两张图看一眼就明白了：

图示中的树形结构，如果终点在最底部，按照传统 BFS 算法的策略，会把整棵树的节点都搜索一遍，最后找到target；而双向 BFS 其实只遍历了半棵树就出现了交集，也就是找到了最短距离。从这个例子可以直观地感受到，双向 BFS 是要比传统 BFS 高效的。

不过，双向 BFS 也有局限，因为你必须知道终点在哪里。比如我们刚才讨论的二叉树最小高度的问题，你一开始根本就不知道终点在哪里，也就无法使用双向 BFS；但是第二个密码锁的问题，是可以使用双向 BFS 算法来提高效率的，代码稍加修改即可：

讯享网

双向 BFS 还是遵循 BFS 算法框架的，只是不再使用队列，而是使用 HashSet 方便快速判断两个集合是否有交集。

另外的一个技巧点就是 while 循环的最后交换q1和q2的内容，所以只要默认扩散q1就相当于轮流扩散q1和q2。

其实双向 BFS 还有一个优化，就是在 while 循环开始时做一个判断：

我的 双向BFS 、 C++实现

讯享网

为什么这是一个优化呢？

因为按照 BFS 的逻辑，队列（集合）中的元素越多，扩散之后新的队列（集合）中的元素就越多；在双向 BFS 算法中，如果我们每次都选择一个较小的集合进行扩散，那么占用的空间增长速度就会慢一些，效率就会高一些。

不过话说回来，无论传统 BFS 还是双向 BFS，无论做不做优化，从 Big O 衡量标准来看，空间复杂度都是一样的，只能说双向 BFS 是一种 trick 吧，掌握不掌握其实都无所谓。最关键的是把 BFS 通用框架记下来，反正所有 BFS 算法都可以用它套出解法。