AI summary
type
status
date
slug
summary
category
tags
icon
password
我多次强调，DFS/回溯/BFS 这类算法，本质上就是把具体的问题抽象成树结构，然后遍历这棵树进行暴力穷举，所以这些穷举算法的代码本质上就是树的遍历代码。
DFS/回溯算法的本质就是递归遍历一棵穷举树（多叉树），而多叉树的递归遍历又是从二叉树的递归遍历衍生出来的。所以我说 DFS/回溯算法的本质是二叉树的递归遍历。
BFS 算法就是遍历一幅图，而图的遍历算法其实就是多叉树的遍历算法加了个 visited 数组防止死循环；多叉树的遍历算法又是从二叉树遍历算法衍生出来的。所以 BFS 算法的本质就是二叉树的层序遍历。
为啥 BFS 算法经常用来求解最短路径问题？
其实所谓的最短路径，都可以类比成二叉树最小深度这类问题（寻找距离根节点最近的叶子节点），递归遍历必须要遍历整棵树的所有节点才能找到最短路径，而层序遍历不需要遍历所有节点就能搞定，所以层序遍历适合解决这类最短路径问题。
在真实的面试笔试题目中，一般不是直接让你遍历树/图这种标准数据结构，而是给你一个具体的场景题，你需要把具体的场景抽象成一个标准的图/树结构，然后利用 BFS 算法穷举得出答案。
比方说给你一个迷宫游戏，请你计算走到出口的最小步数？如果这个迷宫还包含传送门，可以瞬间传送到另一个位置，那么最小步数又是多少？
再比如说两个单词，要求你通过某些替换，把其中一个变成另一个，每次可以替换/删除/插入一个字符，最少要操作几次？
再比如说连连看游戏，两个方块消除的条件不仅仅是图案相同，还得保证两个方块之间的最短连线不能多于两个拐点。你玩连连看，点击两个坐标，游戏是如何判断它俩的最短连线有几个拐点的？
你看上面这些例子，是不是感觉和我们前面学习的树/图结构完全扯不上关系？但实际上只要稍加抽象，它们就是树/图结构的遍历，实在是太简单枯燥了。
下面用几道例题来讲解 BFS 的套路框架，以后再也不要觉得这类问题难解决了。

算法框架

使用队列辅助，孩子都加到队列末尾，当这一层遍历完了才会遍历下一层：
下面我们用几个具体的例题来看看如何运用这个框架。

773. 滑动谜题

给你一个 2x3 的滑动拼图，用一个 2x3 的数组 board 表示。拼图中有数字 0~5 六个数，其中数字 0 就表示那个空着的格子，你可以移动其中的数字，当 board 变为 [[1,2,3],[4,5,0]] 时，赢得游戏。
请你写一个算法，计算赢得游戏需要的最少移动次数，如果不能赢得游戏，返回 -1。
和华容道的规则差不多，华容道应该比这道题更难一些，因为力扣的这道题中每个方块的大小可以看作是相同的，而华容道中每个方块的大小还不一样。
notion image
回到这道题，我们如何把这道题抽象成树/图的结构，从而用 BFS 算法框架来解决呢？
如下图所示：
notion image
每个棋盘状态是一个节点，起点的邻居节点是谁？把数字 0 和上下左右的数字进行交换，其实就是起点的四个邻居节点嘛（由于本题中棋盘的大小是 2x3，所以索引边界内的实际邻居节点会小于四个）。
以此类推，这四个邻居节点还有各自的四个邻居节点，那这不就是一幅图结构吗？
那么我从起点开始使用 BFS 算法遍历这幅图，第一次到达终点时，走过的步数就是答案。
对于这道题，我们抽象出来的图结构也是会包含环的，所以需要一个 visited 数组记录已经走过的节点，避免成环导致死循环。
但是有一个问题，这道题中 board 是一个二维数组，这种可变数据结构是无法直接加入哈希集合的。所以我们还要再用一点技巧，想办法把二维数组转化成一个不可变类型才能存到哈希集合中。常见的解决方案是把二维数组序列化成一个字符串，这样就可以直接存入哈希集合了。
其中比较有技巧性的点在于，二维数组有「上下左右」的概念，压缩成一维的字符串后后，还怎么把数字 0 和上下左右的数字进行交换？
对于这道题，题目说输入的数组大小都是 2 x 3，所以我们可以直接手动写出来这个映射：
这个映射的含义就是，在一维字符串中，索引 i 在二维数组中的的相邻索引为 neighbor[i]：
notion image
这样，无论数字 0 在哪里，都可以通过这个索引映射得到它的相邻索引进行交换了。下面是完整的代码实现：
str.index() 方法用于在字符串中查找 子字符串（子串）的 索引位置，如果找不到，则会抛出 ValueError 异常。
也可以额外在字符串的最后一位记录 0 的索引，交换的时候维护一下，这样就不用每次找了。

752. 打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
题目中描述的就是我们生活中常见的那种密码锁，如果没有任何约束，最少的拨动次数很好算。比方说想拨到 "1234"，那一个个数字拨动就可以了，最少的拨动次数就是 1 + 2 + 3 + 4 = 10 次。
但现在的难点就在于，在拨动密码锁的过程中不能出现 deadends，这样就有一些难度了。如果遇到了 deadends，你该怎么处理，才能使得总的拨动次数最少呢？
千万不要陷入细节，尝试去想各种具体的情况。要知道算法的本质就是穷举，我们直接从 "0000" 开始暴力穷举，把所有可能的拨动情况都穷举出来，难道还怕找不到最少的拨动次数么？
第一步，我们不管所有的限制条件，不管 deadends 和 target 的限制，就思考一个问题：如果让你设计一个算法，穷举所有可能的密码组合，你怎么做？
这个代码已经可以穷举所有可能的密码组合了，但是还有些问题需要解决。
  1. 会走回头路，我们可以从 "0000" 拨到 "1000"，但是等从队列拿出 "1000" 时，还会拨出一个 "0000"，这样的话会产生死循环。
这个问题很好解决，其实就是成环了嘛，我们用一个 visited 集合记录已经穷举过的密码，再次遇到时，不要再加到队列里就行了。
  1. 没有对 deadends 进行处理，按道理这些「死亡密码」是不能出现的。
这个问题也好处理，额外用一个 deadends 集合记录这些死亡密码，凡是遇到这些密码，不要加到队列里就行了。
或者还可以更简单一些，直接把 deadends 中的死亡密码作为 visited 集合的初始元素，这样也可以达到目的。
下面是完整的代码实现：

双向 BFS 优化

下面再介绍一种 BFS 算法的优化思路：双向 BFS，可以提高 BFS 搜索的效率。
你把这种技巧当做扩展阅读就行，在一般的面试笔试题中，普通的 BFS 算法已经够用了，如果遇到超时无法通过，或者面试官的追问，可以考虑解法是否需要双向 BFS 优化。
双向 BFS 就是从标准的 BFS 算法衍生出来的：
传统的 BFS 框架是从起点开始向四周扩散，遇到终点时停止；而双向 BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停止。
为什么这样能够能够提升效率呢？
就好比有 A 和 B 两个人，传统 BFS 就相当于 A 出发去找 B，而 B 待在原地不动；双向 BFS 则是 A 和 B 一起出发，双向奔赴。那当然第二种情况下 A 和 B 可以更快相遇。
notion image
图示中的树形结构，如果终点在最底部，按照传统 BFS 算法的策略，会把整棵树的节点都搜索一遍，最后找到 target；而双向 BFS 其实只遍历了半棵树就出现了交集，也就是找到了最短距离。
当然从 Big O 表示法分析算法复杂度的话，这两种 BFS 在最坏情况下都可能遍历完所有节点，所以理论时间复杂度都是 O(N)，但实际运行中双向 BFS 确实会更快一些。
显然，你必须知道终点在哪里，才能使用双向 BFS 进行优化。
比如上面的密码锁问题和滑动拼图问题，题目都明确给出了终点，都可以用双向 BFS 进行优化。
但二叉树最小高度的问题，起点是根节点，终点是距离根节点最近的叶子节点，你在算法开始时并不知道终点具体在哪里，所以就没办法使用双向 BFS 进行优化。
下面我们就以密码锁问题为例，看看如何将普通 BFS 算法优化为双向 BFS 算法，直接看代码吧：
双向 BFS 还是遵循 BFS 算法框架的，但是有几个细节区别：
  1. 不再使用队列存储元素，而是改用 哈希集合，方便快速判两个集合是否有交集。
  1. 调整了 return step 的位置。因为双向 BFS 中不再是简单地判断是否到达终点，而是判断两个集合是否有交集，所以要在计算出邻居节点时就进行判断。
  1. 还有一个优化点，每次都保持 q1 是元素数量较小的集合，这样可以一定程度减少搜索次数。