前言
唤我沈七就好。
往期专栏:
因为BFS需要靠队列来实现,所以在阅读下面的文章时,需要用先了解一下什么是队列。
可以看我之前对队列的讲解。
基本概念
BFS:是 Breadth-First-Search 简称,即广度优先搜索算法。
与 DFS 一样也是一种用于遍历或搜索树或图的算法。不同的是,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。而 DFS 是沿着树的深度遍历树的节点。
BFS 也被称为层序遍历,即一层一层的遍历,这样效率就高的多,所以相对于 DFS 指数级枚举,BFS 明显是更快的。
因为要同时遍历每一层的结点,所以我们要借助队列保存未被检测的结点。结点按照宽度优先的次序被访问和进出队列。而从队列中取出的顺序即为层序遍历的顺序。
算法思想
BFS 遍历有一个很重要的特点就是,第一个到达目标节点一定是最短路径。
如下图,因为BFS是一层一层的遍历且每一层距离根节点的距离都相同,遍历顺序由内而外,故BFS每到达一个目标节点一定是最短路径。
所以根据这一个特性 BFS 可以解决最短问题。
必备概念
1. STL queue
我一般写BFS喜欢用 STL 的现成实现好的队列 queue。
当然你也可以用数组模拟实现队列。如果想了解如果用数组模拟队列,可以看我这篇文章。
接下来我简单的介绍一下 STL queue 的使用方法。
queue<pair<int,int>> q; q.front() 返回队头元素 q.push() 将元素入队 q.pop() 弹出队头元素
这里我定义的队列类型是 pair ,这是一个二元组,其实简单说这就是一个只有两个变量的结构体。
只不过直接用 pair 来定义方便一些。
定义成二元组,是为了方便表示坐标 ( x , y )。
初次以外还有一些常用的小优化
#define x first #define y second typedef pair<int,int>PII; queue<PII> q;
这样做的目的完全是为了简化代码。
typedef可以重新定义 数据结构 的名称,改成 PII 的单纯是为了简化代码。
fist和second是pair二元组第一和第二个元素,分别通过宏定义用 x 和 y 代替 也是为了简化代码
2 . 偏移量数组
int pos[4][2]={-1,0,0,1,1,0,0,-1}; 扩展方法:偏移量数组
这是一个扩展某一个坐标周围的点的绝佳利器。
详细介绍我在我第一篇博客里有详细介绍,有兴趣的同学可以看看。
常用模板
伪代码模板
void BFS () { ① 初始化队列 ② 将起点入队 ③ 标记起点已经被访问 ④ while( 队列不空时 ) { ⑤ 取出队首元素 u ,存放到 t 变量里 ,u 元素出队 ⑥ 扩展 t 结点 { ⑦ 判重新节点 ⑧ 如果未被访问,且满足要求,记录当前点到起点的距离 ⑨ 标记扩展的新结点 ⑩ 将扩展的新节点入队 } } }
C++ 模板
#define x first #define y second typedef pair<int,int>PII; queue<PII> q; STL 的队列,适用的是一个二元组,方便表示坐标。 q.push(start) ; 初始状态入队 while(!q.empty()) 当队列不空的时候。 PII t=q.front(); q.pop(); 取出队头元素,放到 t 里面去 int pos[4][2]={-1,0,0,1,1,0,0,-1}; 扩展方法:偏移量数组 for(int i=0;i<4;i++) 扩展t结点 { int tx=t.x+pos[i][0]; int ty=t.y+pos[i][1]; if(g[tx][ty]=='#')continue; 判重新节点 if(g[tx][ty]=='.') { dis[tx][ty]=dis[t.x][t.y]+1; 记录当前点到起点的距离; g[tx][ty]='#'; 标记好已经走过路 q.push({tx,ty}); 确定是新节点后入队 } }
或许读者到现在也是懵懵懂懂,笔者能力有限,没办法把为什么这样做讲解的通俗易懂,如果实在想搞明白原理的话,可以去 AcWing 算法基础课中一探究竟。
而在我看来,只要牢记模板,做出题来也不是问题。
下面我就讲解一下能用BFS解决的经典的走迷宫的问题
经典例题:走迷宫
给定一个 n×m 的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。
有一个人位于左上角 ( 1 , 1 )处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问,该人从左上角移动至右下角 ( n , m ) 处,至少需要移动多少次。
分析:提炼题目大意,此题就是求解从迷宫的左上角到迷宫的右下角,在不碰到障碍的最短路径是多少。因为是最短路径问题, 故用 BFS 解决相对容易。
详细的解释都在代码里~
#include<bits/stdc++.h> using namespace std; #define x first #define y second int n,m; typedef pair<int,int>PII; int a[110][110]; 储存地图 int dis[110][110]; 储存距离 int pos[4][2]={-1,0,0,1,1,0,0,-1}; 偏移量数组 void bfs(PII start) { queue<PII>q; q.push(start); 初始状态入队 while(!q.empty()) 队列不空时 { PII t=q.front(); 取出队首元素,存放到 t 变量里 ,元素出队 q.pop(); 元素出队 for (int i = 0; i < 4; i ++ ) 扩展 t 结点 { int tx=t.x+pos[i][0],ty=t.y+pos[i][1]; if(a[tx][ty]==-1||a[tx][ty]==1)continue; 判断是否越界或者碰到障碍 if(a[tx][ty]==0) 如果未被访问, { dis[tx][ty]=dis[t.x][t.y]+1; 记录当前点到起点的距离 a[tx][ty]=-1; 标记扩展的新结点被访问 q.push({tx,ty}); 将扩展的新节点入队 } if(tx==n&&ty==m) 如果到达右下角 { cout<<dis[tx][ty]; 返回右下角到起点的距离 return; } } } } int main() { cin>>n>>m; memset(a, -1, sizeof a); 初始化为 -1 ,这样方便 判断边界 for (int i = 1; i <= n; i ++ ) 从1开始读入地图方便判断边界,这样地图都会被初始化的 -1 包围 for (int j = 1; j <= m; j ++ ) 这样判断扩展的点是否越界时,只要判断是不是 -1 即可 { cin>>a[i][j]; } PII start; 定义一个二元组,储存起点,传入到BFS函数里 start.x=1,start.y=1; bfs(start); return 0; }
完结散花
ok以上就是对 暴力搜索之BFS 的全部讲解啦,很感谢你能看到这儿啦。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我,我后期再补充完善。
题目练习
检验知识是否学会当然是不断刷题啦,下面我给出一部分DFS相关的一些经典题目。
后续如果我有时间就更新这部分知识的题解,到时候就可以配套学习啦。
参考文章
参考文献
https://www.acwing.com/activity/content/19/