安徽鲲鹏建设集团有限公司网站,风云榜,注册网站后如何注销账号,荣成市城乡建设局网站算法介绍#xff1a;
广度优先搜索#xff08;Breadth-First Search#xff0c;简称BFS#xff09;是一种遍历或搜索树和图的算法#xff0c;也称为宽度优先搜索#xff0c;BFS算法从图的某个节点开始#xff0c;依次对其所有相邻节点进行探索和遍历#xff0c;然后再…算法介绍
广度优先搜索Breadth-First Search简称BFS是一种遍历或搜索树和图的算法也称为宽度优先搜索BFS算法从图的某个节点开始依次对其所有相邻节点进行探索和遍历然后再对这些相邻节点的相邻节点进行探索直到遍历完所有的节点。BFS算法使用队列来辅助实现将起始节点放入队列中然后依次取出队列中的节点访问其相邻节点并将其加入队列。这样可以保证从起始节点出发依次按照距离顺序遍历节点。BFS常用于寻找最短路径因为它按照从起点到每个节点的距离来探索节点。
在ACM、蓝桥杯等著名竞赛中BFS算法是比较重要的特别是在蓝桥杯中每一年几乎都要考DFS/BFS算法。BFS算法在OI赛中用处非常大可以通过DFS/BFS暴力的方式可以拿到部分分数蓝桥杯一般可以拿到20%的分数有的甚至高达50%是暴力得分的不二之选。 基本步骤
BFS算法通常使用队列来实现BFS算法的具体步骤如下
创建一个队列将起始节点加入队列创建一个集合用于存储已经访问过的节点从队列中取出一个节点并将其标记为已访问访问该节点的所有相邻节点如果相邻节点未被访问则将其加入队列重复步骤3和步骤4直到队列为空。
BFS算法可以用来解决一些问题例如图的遍历、最短路径搜索等。由于BFS算法保证了按照距离顺序遍历节点因此可以用来寻找最短路径。另外BFS算法还可以用来判断图是否连通即从一个节点是否可以到达另一个节点。 图解算法
下面放一张我们学校ACM在大一培训时使用的一张动态BFS/DFS步骤图。注红色遍历为BFS、黄色遍历为DFS。绿色为起点紫色为终点黑色为障碍物 由上图中我们可以看出BFS的遍历为四周扩散用我们学长的话说就是周围每个点都尝试一下无脑走直到找到终点。由此我们可以看出来BFS这种无脑走必定会导致时间复杂度非常高如果终点离起点非常远那么几乎每个点都要遍历一下这样的话BFS这种算法就不适合了BFS适合于点少的图求最短距离之类的。BFS一般通过队列来实现。
下面我们将以5*5的网格考虑{上、右上、右、右下、下、左下、左、左上}八个方向遍历顺序为{上、右上、右、右下、下、左下、左、左上}由上开始顺时针方向顺序可按照自己的想法顺序不一定固定给大家模拟实现一下过程。
注为方便表示对于下面的叫法特此说明起点.上表示起点上面的格子起点.上右表示起点右上方的格子其他方向类似起点.上.上右表示起点的上面格子的右上方格子。
第一步
初始起点入队标记起点vis[起点]true说明起点已经被访问了判断起点是否为终点起点出队很明显不是那么从起点周围按照{上、右上、右、右下、下、左下、左、左上}的顺序八个方向遍历每一个格子将它们一一入队并且将它们标记为已经访问过了即vis[八个方向]true。 第二步
由于我们第一步按照{上、右上、右、右下、下、左下、左、左上}的顺序入队的此时队中的顺序是起点的{上、右上、右、右下、下、左下、左、左上}方向那么此时出队的第一个是{上}方向我们去遍历{上}方向的八个方向由于{上}方向的八个方向中{上、右上、左上}三个方向下标越界其他的都已经被访问过了不合法直接continue忽略掉{上}方向遍历完成{上}方向出队。 第三步
此时要出队的为{上右}方向先标记{上右}方向然后遍历{上右}方向的八个方向我们发现只有{上右}方向的{右}方向跟{下右}方向是合法的其他的方向要么下标越界要么已经被访问了那么把{上右}方向的{右}方向跟{上右}方向的{下右}方向入队并且标记它们的vis为true。 第四步
此时队头的为起点的{右}方向将它出队判断它不是终点那么遍历它的八个方向发现只有它的{右下}方向是合法的其他方向都已经被标记过了。那么将vis[右下]标记为true将它的右下方向入队。 第五步
此时队头的为起点的{下右}方向将它出队判断它不是终点那么遍历它的八个方向发现它的{右下、下、左下}方向是合法的其他方向都已经被标记过了。那么将vis[右下、下、左下]标记为true并且将其入队。此时我们发现它的右下方向是终点了已经在栈队当中再经过八次出队那么就是这个出队的点就是终点了判断完成后此时BFS搜索就结束了由于下面都是相同的出队入队步骤下面不再详解。 算法模板
首先我们需要一个队列来辅助BFS实现还需要一个初始化的输入数组还有一个标记数组。先找到BFS的起点跟终点确定好之后先把起点vistrue把起点入队然后进入BFS函数进入BFS函数一般先是一个大while循环来管理队列的入队、出队。由于点都是二维的我们一般都是用pair或者结构体来表示点新建一个点来存储队头的信息存完就可以让队头出队了。然后判断是否到达了目标结点一个if判断下面就是跟dfs一样一个for循环遍历周围所有的点不合法的直接continue掉合法的标记完vis后入队有的题目会有回溯像在部分最短路搜索。
queuenode q;
void bfs(){while(!q.empty()){node tmpq.top();//node为(x,y)结构体q.pop();//出队if(到达目标终点){更新return;}//有的会有剪枝for(int i0;im;i){//m个方向int dxtmp.xbx[i];int dytmp.yby[i];if(下标越界){continue;}if(已经被标记过了){continue;}//否则就是合法的vis[dx][dy]1;//先标记q.push(node{dx,dy});//再新点入队}}
} 算法例题
现在各大算法刷题网站上bfs题目非常的多bfs题目的变化也比较多现在各种各样的题目层出不穷bfs考察的还是主要分为图的遍历问题、最短路问题、连通块搜索等下面博主选取几个比较具有代表性的给大家讲解一下加深理解一下bfs算法。 一、图的遍历问题
迷宫问题
【题目描述】
一天Extense在森林里探险的时候不小心走入了一个迷宫迷宫可以看成是由n×n的格点组成每个格点只有2种状态.和#前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时他只能移动到东南西北或者说上下左右)四个方向之一的相邻格点上Extense想要从点A走到点B问在不走出迷官的情况下能不能办到。如果起点或者终点有一个不能通行为#则看成无法办到。
【输入】
第1行是测试数据的组数k后面跟着k组输入。每组测试数据的第1行是一个正整数n(1≤n≤ 100)表示迷宫的规模是n×n的。接下来是一个n×n的矩阵矩阵中的元素为.或者#。再接下来一行是4个整数ha,la,hb,lb描述A处在第ha行第la列B处在第hb行第lb列。注意到halahblb全部是从0开始计数的。
【输出】
k行每行对应一个输出如果能到达则输出YES否则输出NO。
【样例】
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0YES
NO
解题思路
这类问题属于图的遍历问题属于BFS题里面最简单的问题直接利用BFS的思想遍历即可判断是否能到达。之所以选这个题是先让刚入门的小萌新熟悉一下BFS的步骤、思想。大佬可跳过此题。
AC代码
#includeiostream
#includequeue
#includecstring
using namespace std;
int n,t;
char ch[105][105];
bool flagfalse,vis[105][105];
int sx,sy,fx,fy;
int bx[]{0,0,1,-1},by[]{1,-1,0,0};//方向数组
struct node{int x,y;
};
queuenode q;//队列
void bfs(){while(!q.empty()){node tmpq.front();//取队头元素q.pop();//出队if(tmp.xfxtmp.yfy){//目标状态flagtrue;return;}for(int i0;i4;i){//周围四个方向搜索int dxtmp.xbx[i],dytmp.yby[i];if(dx0||dxn||dy0||dyn){//下标越界continue;}if(vis[dx][dy]){//已经被访问过continue;}if(ch[dx][dy]#){//墙壁continue;}vis[dx][dy]1;//先标记q.push(node{dx,dy});//再入队}}
}
int main(){cint;while(t--){cinn;for(int i0;in;i){for(int j0;jn;j){cinch[i][j];}}cinsxsyfxfy;flagfalse;memset(vis,0,sizeof(vis));while(!q.empty()){//多次输入防止上次队列的影响q.pop();}vis[sx][sy]1;q.push(node{sx,sy});//起点入队bfs();cout(flag?YES:NO)endl;}return 0;
} 二、最短路问题
AcWing 1102. 移动骑士
给定一个 n∗n 的棋盘以及一个开始位置和终点位置。
棋盘的横纵坐标范围都是 0∼n−1。
将一个国际象棋中的骑士放置在开始位置上请问将它移动至终点位置至少需要走多少步。
一个骑士在棋盘上可行的移动方式如下图所示 输入格式
第一行包含整数 T表示共有 T 组测试数据。
每组测试数据第一行包含整数 n表示棋盘大小。
第二行包含两个整数 x,y 用来表示骑士的开始位置坐标 (x,y)。
第三行包含两个整数 x,y 用来表示骑士的终点位置坐标 (x,y)。
输出格式
每组数据输出一个整数表示骑士所需移动的最少步数每个结果占一行。
数据范围
4≤n≤300 0≤x,y≤n−1
输入样例
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1输出样例
5
28
0
解题思路
这道题跟马走日那一题几乎是一样的但是不一样的是这道题是求的最小步数。这就是最短路问题了。还是跟之前的BFS步骤一样就是在目标状态那里多了一个更新最小步数。这道题比前面的图的遍历问题难一点点注意BFS是不需要回溯的否则会陷入死循环。
AC代码
#includeiostream
#includecstring
#includequeueusing namespace std;
int t,n;
int sx,sy,fx,fy;//(sx,sy)起点,(fx,fy)终点
struct node{//点结构体int x;int y;int dep;//步数
}Node;
int dx[]{1,1,2,2,-1,-1,-2,-2};//方向数组
int dy[]{2,-2,1,-1,2,-2,1,-1};
bool vis[305][305];//标记数组
int sum0x3f3f3f;//最小步数
queuenode q;void bfs(){while(!q.empty()){auto tmpq.front();q.pop();if(tmp.xfxtmp.yfy){//目标状态更新最小步数summin(sum,tmp.dep);return;}for(int i0;i8;i){//八个方向遍历Node.xtmp.xdx[i];Node.ytmp.ydy[i];if(Node.x0||Node.y0||Node.xn||Node.yn){//下标越界continue;}if(vis[Node.x][Node.y]1){//已经被访问过continue;}Node.deptmp.dep1;//步数更新vis[Node.x][Node.y]1;//先标记q.push(Node);//再入队}}
}int main(){cint;while(t--){memset(vis,false,sizeof(vis));//多组输入置0sum0x3f3f3f;//初始最大值cinnsxsyfxfy;vis[sx][sy]1;//先标记起点while(!q.empty()){//清空队列q.pop();}q.push(node{sx,sy,0});//起点步数为0bfs();coutsumendl;}return 0;
} 洛谷 P1379 八数码难题
题目描述
在 3×3 的棋盘上摆有八个棋子每个棋子上标有 1 至 8 的某一数字。棋盘中留有一个空格空格用 0 来表示。空格周围的棋子可以移到空格中。要求解的问题是给出一种初始布局初始状态和目标布局为了使题目简单,设目标状态为 123804765找到一种最少步骤的移动方法实现从初始布局到目标布局的转变。
输入格式
输入初始状态一行九个数字空格用 0 表示。
输出格式
只有一行该行只有一个数字表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。
输入
283104765输出
4样例解释 图中标有 0 的是空格。绿色格子是空格所在位置橙色格子是下一步可以移动到空格的位置。如图所示用四步可以达到目标状态。并且可以证明不存在更优的策略。
解题思路
这道题在博主做题的感觉来说题目质量是非常高的思维也非常有高度建议大家好好学一下。八数码非常类似于中国的数独游戏。在解决此题时一个布局对应一个字符串也就是一个状态可以理解为一个布局转换为目标布局所需要的最小步数。
下面讲解一下如何解决此题我们发现每一个字符串就是一个状态最短距离还需要记录步数那么我们就想到了map键值映射由一个字符串对应初始状态到此状态的最小步数。例如d[123048567]2表示由初始状态到目标状态最小步数为2步完成。其次是‘0’字符一维下标跟二维下标位置转换的技巧我们发现每一次都是‘0’字符空格与四个方向的数字进行交换属于空格的BFS对于一维下标可以通过除3为横坐标模3为纵坐标3*3棋盘由二维转为一维坐标倒过来即可即3*横坐标纵坐标。刚开始可以使用find()函数查找‘0’字符的下标然后转化为布局中的二维坐标。每完成一步就要交换格子交换完成就得到一种新的布局那么我们可以用count()函数去map里面查找如果有这种状态说明之前用更小的步数就已经到达过了没必要更新了。如果没有这种状态那么我们就为它赋值最小步数。最后还要还原对于这个题来说是必要的因为四个方向搜索都是以‘0’为基础的for循环一次把他改变了后面的3次循环就在它前一个状态的基础上。这样交换操作就乱了。
视频讲解 请看B站up主董晓算法—点击直达—博主感觉董晓老师讲的非常好本题思路按照董晓老师讲解来写的。大家可以去看看下面第二张图片来自董晓老师讲解。 AC代码
#includeiostream
#includealgorithm
#includecstring
#includequeue
#includeunordered_mapusing namespace std;int dx[]{-1,0,1,0},dy[]{0,1,0,-1};//方向数组
unordered_mapstring,int d;//考虑map键值对映射,状态映射步数
queuestring q;//棋盘状态布局int bfs(string strat){string end123804765;//目标状态q.push(strat);//初始状态d[strat]0;while(q.size()){auto sq.front();q.pop();if(send){//目标状态return d[s];}int ks.find(0);//下标位置转化int xk/3;int yk%3;for(int i0;i4;i){//四个方向搜索int axdx[i];int bydy[i];if(a0||a3||b0||b3){//下标越界continue;}int distanced[s];//记录步数swap(s[k],s[3*ab]);//交换if(!d.count(s)){//新的布局d[s]distance1;q.push(s);}swap(s[k],s[3*ab]);//还原}}return -1;//无法到达
}int main(){string strat;for(int i0;i9;i){char ch;cinch;stratch;}coutbfs(strat)endl;return 0;
} 三、连通块问题
第十四届省赛大学B组C/C岛屿个数
到目前为止我做过像连通块问题的题用BFS解的就这一个比较好这一道题跟连通块有结合博主才把它归到了连通块问题来。具体的讲解跟AC代码请看我这一篇文章文章单独讲解了这一道题由于文章长度限制这里不再详解请移步下面链接。
第十四届省赛大学B组C/C岛屿个数-CSDN博客文章浏览阅读1.1k次点赞30次收藏14次。这不是普通的DFS/BFS搜索题看着很像最少连通块但是题目中又有了新的定义就是在陆地环里面被陆地包围也算属于此外围岛屿那么我们就也要判定这种环岛屿博主的思路是先BFS也可DFS找出连通块的个数四个方向建一个vector把连通块的起点存进去方便去找环岛屿只要有一个起点或者此连通块任意一个点此连通块的点便可通过移动一网打尽再BFS或者DFS判定该岛屿是否属于这种环岛屿不属于就结果加一属于就不用加。对于 100% 的评测用例1≤T≤101≤M,N≤50。https://blog.csdn.net/m0_73633807/article/details/137248445?spm1001.2014.3001.5501 图形搜索算法还有一种是DFS请看博主上一篇文章数据结构与算法——DFS(深度优先搜索)
制作不易如果对你有所帮助请三连支持博主持续创作感谢各位大佬的支持。
