BFS（广度优先遍历）算法框架
回顾 动态规划/DFS(深度优先搜索)/回溯 算法框架
借用二叉树来回顾一下之前学习的 动态规划/DFS(深度优先搜索)/回溯 三种框架：
动态规划框架：
//自顶向下递归的动态规划
int dp(状态1,状态2,...){
for(选择 in 所有可能的选择){
//状态因为选择发生改变
result = 求最值(result,dp(状态1,状态2,...))
}
return result;
}
//自底向上迭代的动态规划
dp[0][0][...] = base case;
//进行状态转移
for 状态1 in 状态1 的所有取值{
for 状态2 in 状态2 的所有取值{
for...{
dp[状态1][状态2][...] = 求最值(选择1，选择2，...);
}
}
}动态规划的本质是将问题分解为多个子问题，找出最优子结构，得出状态转移方程，最后递推出结果。
重叠子问题、最优子结构、状态转移方程 动态规划三要素
DFS(深度优先搜索) 与回溯框架：
//多叉树节点
class Node{
int key;
int val;
Node[] children;
}
//DFS 算法把[做选择][撤销选择]的逻辑放在for循环外面
void dfs(TreeNode root){
if(root == null) return;
//做选择
System.out.println("进入%s节点",root.key);
for(TreeNode child:root.children){
dfs(child);
}
//撤销选择
System.out.println("退出%s节点",root.key);
}
//回溯算法把[选择][撤销选择]的逻辑放在for循环里面
void backtrack(TreeNode root){
if(root == null) return;
for(TreeNode child:root.children){
//做选择
System.out.println("站在从%s节点到%s节点的树枝上",root.key,child.key);
backtrack(child);
//撤销选择
System.out.println("将要离开从%s节点到%s节点的树枝",child.key,root.key);
}
}-
动态规划属于分解问题的思路，着重点在于每棵子树。
-
DFS算法属于遍历的思路，着重点在于每个节点。 -
回溯算法属于遍历的思路，着重点在于每个树枝。
BFS(广度优先搜索) 算法详解
BFS的核心思想：把一些问题抽象成图，从一个点开始，向四周扩散。BFS 算法一般都会借助队列来遍历图中的所有节点，每遍历到一个新节点，就把与这个节点相连的其他结点加入到队列之中。Dijkstra 算法就是典型的例子。
BFS 与 DFS 的核心区别在于：BFS找到的路径一定是最短的，但代价就是空间复杂度可能比DFS大很多，从后文的代码框架就很容易看出来了。
BFS算法框架
在介绍框架之前，我们先了解一下BFS算法使用最多的场景，问题的本质就是让你在一个图中找到【start】到终点【target】的最短路径，这个例子听起来枯燥，但其实BFS算法都在干这个事 ，把这个本质弄清楚了，解决经过包装的各种问题才能得心应手嘛。
这个广义的描述可以有各种变体:
-
比如走迷宫，有的格子是围墙，那么从起点到终点的最短距离是多少？如果有的格子会有传送门【实施瞬间传送】呢，最短距离又是多少？
-
再比如说两个单词，要求你通过某些替换，每次替换可以增加、删除或替换一个字符，最少要替换几次呢？（这个在动态规划系列里提到过，
dp[i][j]表示word1[0...i]转换到word2[0...j]所需要的最少操作数） -
再比如连连看游戏，两个方块消除的条件不仅是图案相同，还得保证两个方块之间的最短连线不能超过两个拐点。玩连连的时候，游戏是如何判断最短连线不超过两个拐点的呢？
变体有很多，但本质就是在一个【图】中，找【start】到【target】的最短路径罢了，只是加了一些限制条件。
BFS框架：
int BFS(Node start, Node target){
queue<Node> q; //存储接下里要遍历的节点
set<Node> visited; //存储已经遍历过的节点
q.push(start);
visited.insert(start);
int step = 0;
//开始广度优先搜索
while(!q.empty()){
//遍历这一层的节点
int num = q.size();
for(int i = 1;i <= num;i++){
step++;
Node cur = q.front();
q.pop();
if(cur == target){
return step;
}
//如果此节点不是目标节点，则将此节点的邻接节点推入队列，继续访问下一个节点
for(Node x:cur.adj()){
if(visited.count(x) == 0){
q.push(x);
visited.insert(x);
}
}
}
}
//走到这里说明已经遍历完图中的所有节点，表明图中没有target
}队列q 为BFS的核心数据结构，cur.adj()泛指当前节点cur的所有邻接节点，如果这个图我们用邻接表的形式存储的话，cur.adj()其实就是节点cur对应的邻接链表，类似的在二维数组中，cur上下左右四面的位置就是相邻节点，也就是邻接节点。visited的主要作用是为了防止走回头路，已经遍历过的节点就不要再遍历了，这对于大部分可回头的问题是必须的，但是对于二叉树这种（没有子节点指向父节点的指针）是不需要的。
二叉树的最小高度(LeetCode111)
我们通过 判断二叉树的最小高度 这道题来实践一下BFS框架。
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5
提示：
-
树中节点数的范围在
[0, 105]内 -
-1000 <= Node.val <= 1000
怎么套BFS框架呢，简单分析后不难发现，这道题的root根节点 和 最靠近root根节点的叶子节点 就是BFS框架里的【start】与【target】。
if(cur.left == null && cur.right == null){
//一检测到叶子节点，立马结束
做出相应操作并结束程序，返回结果
}
现在我们只要对BFS框架稍加改造，即可得出结果：
int BFS(Node start){
queue<Node> q; //存储接下里要遍历的节点
set<Node> visited; //存储已经遍历过的节点
q.push(start);
visited.insert(start);
int level = 0; //记录层数
//开始广度优先搜索
while(!q.empty()){
level++;
//遍历这一层的节点
int num = q.size();
for(int i = 1;i <= num;i++){
Node cur = q.front();
q.pop();
//找到叶子节点，返回当前遍历层数即可
if(cur.left == null && cur.right == null){
return level;
}
/*//如果此节点不是目标节点，则将此节点的邻接节点推入队列，继续访问下一个节点
for(Node x:cur.adj()){
if(visited.count(x) == 0){
q.push(x);
visited.insert(x);
}
}*/
if(cur.left != null){
q.push(cur.left);
}
if(cur.right != null){
q.push(cur.right);
}
}
}
//走到这里说明已经遍历完图中的所有节点，表明图中没有target
}这里注意for循环与while的配合，while循环控制一层一层往下走，for循环利用num变量从左到右遍历每一层二叉树节点：
这一点非常重要，这个形式在BFS问题中非常常见，但是在 Dijkstra 算法模板框架 中我们修改了这种代码模式，读完并理解本文后你可以去看看 BFS 算法是如何演变成 Dijkstra 算法在加权图中寻找最短路径的。
话说回来，二叉树本身是很简单的数据结构，我想上述代码你应该可以理解的，其实其他复杂问题都是这个框架的变形，再探讨复杂问题之前，我们解答两个问题：
-
为什么
BFS可以找到最短路径，而DFS不行？
首先，看BFS的逻辑，level每增加一步，队列中的所有节点都往前迈一步(队列中存的是一层一层的节点)，这保证了第一次到达【target】时的步数是最小的。！！！BFS只是找到了最短路径的长度（从【start】到【target】的最少步数而已）。
如果想找到最短路径的整个路径，即最短路径经过了哪些节点，需要从【target】开始回溯，拿这个【求二叉树的最小深度】举例，我们从终点【target】开始回溯，依着父节点找，一直找到【start】，这条路径就是我们要找的最短路径。
其实DFS也能找到最短路径，只是DFS需要遍历所有的分支，遍历完才能得出最短的路径，而且DFS是依靠递归堆栈来记录走过的路径，这些缺点大大增加了时间复杂度，而BFS借助队列一次实行【齐头并进】，不用遍历完树的所有节点就可找到最短距离。
形象地说，DFS是线，BFS时面，DFS单打独斗，一个节点就往深处走，BFS是集体行动，一层遍历完了之后再进入下一层。
-
为什么
BFS可以找到最短路径，而DFS不行？
BFS虽然可以找到最短距离，但是空间复杂度较大，而DFS所需要的空间复杂度就比较小。
还是拿刚刚的【二叉树最小深度】举例，在最坏情况下，BFS的空间复杂度为最后一层的节点个数，也就是N/2,用Big O 表示的话也就是
O(N),而DFS的空间复杂度也就是递归堆栈所占空间，最坏情况下为O(logN)。
一般来说，一般在寻找最短路径的时候用BFS，其他时候还是用DFS
LeetCode752 打开转盘锁
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
示例 1:
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202" 输出：6 解释： 可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。 注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的， 因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:
输入: deadends = ["8888"], target = "0009" 输出：1 解释：把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" 输出：-1 解释：无法旋转到目标数字且不被锁定。
提示：
-
1 <= deadends.length <= 500 -
deadends[i].length == 4 -
target.length == 4 -
target不在deadends之中 -
target和deadends[i]仅由若干位数字组成
这道题的密码锁和我们行李箱上的密码锁很类似，如果没有deadends限制的话，我们直接向着密码拨动就行了【第一个位置的数字转换成密码对应位置的数字需要几步 + ... + 最后一个位置的数字转换成密码对应位置的数字需要几步】。
但是现在有了deadends这个限制条件，也就是说不能直接拨过去，可能需要绕一段路，这又该如何计算最少步数【最短距离】呢？
第一步，我们不管target与deadends限制条件，就思考一个问题，该怎么设计一个算法穷举所有可能的密码组合？
穷举呗，再贴合题目一点，如果只转一下锁，有多少种可能？很显然，有八种。四个位置，每个位置可以向上转，也可以向下转，总共八种可能。
比如从初始密码状态‘0000’开始，经过一次转锁操作，可以转成‘1000’,’9000’,’0100’,’0900’...等八种密码状态，再以这八种密码状态为基础，每个状态又可以延伸为另外八种状态。
仔细想想，这个问题就可以抽象为图的问题，每个节点有八个邻接节点，又让你求最短距离，这不就是典型的BFS框架吗，我们先写一个适应这个问题的简陋的【先不考虑限制条件和target】的BFS框架：
//将s[j]向上拨一格
string plusOne(string s,int j){
//将字符串转换成字符数组进行操作，方便对单个字符进行处理
char res[s.length()];
strcpy(res, s.c_str());
if(res[j] == '9'){
res[j] = '0';
}else{
res[j] += 1;
}
string result(res);
return result;
}
//将s[j]向下拨一格
String minusOne(string s,int j){
//将字符串转换成字符数组进行操作，方便对单个字符进行处理
char res[s.length()];
strcpy(res, s.c_str());
if(res[j] == '0'){
res[j] = '9';
}else{
res[j] -= 1;
}
string result(res);
return result;
}
//BFS框架，打印出所有密码
void BFS(String target){
queue<string> q;
q.push('0000');
while(!q.empty()){
int sz = q.size();
for(int i = 1;i < sz;i++){
string cur = q.front();
q.pop();
//输出遍历的所有节点
cout << cur << endl;
//将cur的相邻节点加入到队列里
for(int j = 0;j < 4;j++){
string up = plusOne(cur, j);
string down = minusOne(cur, j);
q.push(up);
q.push(down);
}
}
/*在这里增加步数*/
}
return; // 结束BFS遍历
}这段代码可以遍历所有密码组合，但是仍然不能解决问题，有以下问题还没解决：
-
会走回头路，比如说我们从‘0000’拨到‘1000’,但是从队列中拿出‘1000’时，可能还会拨出‘0000’，这样的话会产生死循环，我们需要建立一个
visited集合。 -
没有终止要求，按照要求，遍历到【target】时就要结束遍历并返回拨动的次数。
-
没有对
deadends的处理，按道理这些【死亡密码】是不能出现的，也就是说你遇到这些密码时需要跳过。
只要稍作修改就可得出最终代码：
int openLock(vector<string>& deadends, string target) {
// 记录需要跳过的死亡密码
unordered_set<string> deads;
for (string s : deadends) {
deads.insert(s);
}
// 记录已经穷举过的密码，防止走回头路
unordered_set<string> visited;
queue<string> q;
// 从起点开始启动广度优先搜索
int step = 0;
q.push("0000");
visited.insert("0000");
while (!q.empty()) {
int sz = q.size();
/* 将当前队列中的所有节点向周围扩散 */
for (int i = 0; i < sz; i++) {
string cur = q.front();
q.pop();
/* 判断是否到达终点 */
if (deads.count(cur))
continue;
if (cur == target)
return step;
/* 将一个节点的未遍历相邻节点加入队列 */
for (int j = 0; j < 4; j++) {
string up = plusOne(cur, j);
if (!visited.count(up)) {
q.push(up);
visited.insert(up);
}
string down = minusOne(cur, j);
if (!visited.count(down)) {
q.push(down);
visited.insert(down);
}
}
}
/* 在这里增加步数 */
step++;
}
// 如果穷举完都没找到目标密码，那就是找不到了
return -1;
}
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
15
0- 0
已为社区贡献1条内容
所有评论(0)