广度优先搜索（BFS最基础）
2026-05-20 22:00:37
发布于：上海
注：本人语文不好，所以语句可能会不通顺。我本次是给新手为BFS打上基础的，并没有拓展，谢谢
本次肝了大概4小时左右，且分了3次写
众所周知，发一篇帖子需要头图
这里是我们毕业群里的图片
我们先用一道题作为本次文章的引导
A83422.幅優先探索
这道题的答案是这样的：
#include<iostream>
#include<queue>
using namespace std;
int n,m,sx,sy,gx,gy;
char a[55][55];
bool vis[55][55];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
struct node{
int x,y,step;
};
void BFS(){
queue<node> q;
q.push({sx,sy,0});
vis[sx][sy]=true;
while(q.size()){
node now=q.front();
q.pop();
if(now.x==gx&&now.y==gy){
cout<<now.step;
return;
}
for(int i=0;i<4;i++){
int nx=now.x+dx[i],ny=now.y+dy[i];
if(nx<0||nx>n+1||ny<0||ny>m+1){
continue;
}
if(vis[nx][ny]||a[nx][ny]=='#'){
continue;
}
vis[nx][ny]=true;
q.push({nx,ny,now.step+1});
}
}
}
signed main(){
cin>>n>>m>>sx>>sy>>gx>>gy;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
BFS();
return 0;
}
没错，这就是广度优先搜索（BFS）
什么是广度优先搜索（BFS）
首先，我们认识一下BFS是什么
这个算法是从起点到终点的最短距离
E.g
⏰不好不好，上学要迟到了！现在即将要到校的你，也即将要迟到，刚好，你有一块可以查看在现在的位置上于学校所有（不包括特别长）路径，手表上显示了：
F # # #
. . . .
. # # .
S . . .
S表示start，意思是开始
F表示finish，表示结束
.表示可行走路径
#表示不可行走路径
“想啥了？当然一直往前跑啊！”
没错，假若你选另一条到的话，那么你一定到学校后被狠狠骂一顿，然后罚站【doge】
当然，如果你仔细看（？），你会发现刚才说的一直往前跑的那条路就是最短的那条路，既省时，又省力
好了，我们回归主题，接下来，我们将拆解这道题目的答案，然后一 一讲一下
START😂
首先我们来看这段代码：
int n,m,sx,sy,gx,gy;
char a[55][55];
bool vis[55][55];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
这里的n m分别指这个迷宫的长和宽，而sx sy是指起始位置，而这里的gx gy是终点位置
char a[55][55];是指这个迷宫的"地图"
最后一行int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};,这一行现在看起来好像不知道是什么作用，不过先让子弹飞一会儿，我们接下来看后面一段：
struct node{
int x,y,step;
};
这里用了struct类型结构，为了方便表示位置和步数，直接用node里的坐标和步数就行了
再看下一段：
queue<node> q;
q.push({sx,sy,0});
vis[sx][sy]=true;
我们先创造一个队列q,类型node
再接着，我们把起始位置和起始步数加入队列，接着把没有走过的路径把它标称走过的路径
再来看个大部分
while(q.size()){
node now=q.front();
q.pop();
if(now.x==gx&&now.y==gy){
cout<<now.step;
return;
}
for(int i=0;i<4;i++){
int nx=now.x+dx[i],ny=now.y+dy[i];
if(nx<0||nx>n+1||ny<0||ny>m+1){
continue;
}
if(vis[nx][ny]||a[nx][ny]=='#'){
continue;
}
vis[nx][ny]=true;
q.push({nx,ny,now.step+1});
}
}
好的，现在我们需要图讲述这大块的代码了
我们再拆几部分
Part 1
node now=q.front();
q.pop();
我们现在看这张图：
为了表示方便，我们将横轴为,数轴为,位置表示
所有的墙，都表示为#（图中和文字表示）
我们假设是起点，是终点
以之前的
queue<node> q;
q.push({sx,sy,0});
vis[sx][sy]=true;
现在，里的队列是：
[{7,1,0}]
再回来看，现在now的值是
{7,1,0}//此处可能不规范
到第二行后，为空队列
Part 2
if(now.x==gx&&now.y==gy){
cout<<now.step;
return;
}
这个判断条件是指我们是否在终点,如果是，输出最短步数，退出此函数[1]
因为在条件语句里的意思是：
在now点的x等同于终点的x，now点的y等同于终点的y
Part 3
for(int i=0;i<4;i++){
int nx=now.x+dx[i],ny=now.y+dy[i];
if(nx<0||nx>n+1||ny<0||ny>m+1){
continue;
}
if(vis[nx][ny]||a[nx][ny]=='#'){
continue;
}
vis[nx][ny]=true;
q.push({nx,ny,now.step+1})
}
这里是对于后面走的路线的情况
之前我说的先让子弹飞一会儿就在这里"停止"了
这里是探查下一步路径的作用
现在，我们再次回到之前的代码块
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
dx管理的是左右探查路径
而dy则是上下探查路径
例如，我们还是以之前的图片的位置
现在在探查下一步左右路径（如图），但这个时候有人会说：
探查右的话这里就出地图边界了
没错，所以再看这一块
if(nx<0||nx>n+1||ny<0||ny>m+1){
continue;
}
这里的nx<0指的是出地图左边界，而nx>n+1是出地图右边界
ny<0是指出地图上边界，ny>m+1是指出地图下边界
现在，我们将这些情况合并起来，就是这里万万不可出现的情况
所以，这里使用continue是为了防止继续执行下去，否则要丸辣
现在大家看到这里小部分可能一脸疑惑❓
如果边界出了，有什么严重？
以后
nx和ny会被当下标使用，而后面可能会RE(runtime error，指运行时错误，与编译错误（CE)不同）
Part 4
if(vis[nx][ny]||a[nx][ny]=='#'){
continue;
}
这里是一个路径判断，指的是
是否有墙？是走过的路径吗？
因为墙视为不可行走路，而走走过路径的话那将可能是到处乱逛,所以也是排除在外的情况
Part 5
vis[nx][ny]=true;
q.push({nx,ny,now.step+1})
成功后，这里将为路过路径，且进入q队列
运行
以本张图片为例
假设起点为,终点为{7,3)
接着探查路径，发现
只有一个方向可走，这时候，q队列为
[{6,1,1}]
再次继续探查，发现
有两条路径可走，这时候，q队列为
[{6,2,2}{5,1,2}]
以此类推，直到
后结束，
最后最短步数为4
我们再来看一道题：
A8046.仙岛求药
虽然在起点和终点进行了一些标志，让自己去找起点和终点，不过还是套模板就行了
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int N,M,sx,sy,fx,fy;
char a[2005][2005];
bool vis[2005][2005];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct node{
int x,y,step;
};
int BFS(){
queue<node> q;
q.push({sx,sy,0});
vis[sx][sy]=true;
while(q.size()){
node now=q.front();
q.pop();
if(now.x==fx&&now.y==fy){
return now.step;
}
for(int i=0;i<4;i++){
int nx=now.x+dx[i];
int ny=now.y+dy[i];
if(nx<1||nx>2000||ny<1||ny>2000){
continue;
}
if(!vis[nx][ny]&&a[nx][ny]!='#'){
vis[nx][ny]=true;
q.push({nx,ny,now.step+1});
}
}
}
return -1;
}
int main(){
cin>>M>>N;
for(int i=1;i<=M;i++){
for(int j=1;j<=N;j++){
cin>>a[i][j];
if(a[i][j]=='@'){
sx=i;
sy=j;
}
if(a[i][j]=='*'){
fx=i;
fy=j;
}
}
}
memset(vis,false,sizeof(vis));
int result=BFS();
cout<<result;
}
thanks
我在次必须要谢谢Deepseek人工智能AI,我为了这篇文章，问了他很多问题，他每次都会耐心的回复我，曾经我自学BFS的时候我就是投一个题目，跟他慢慢去解析，我因此也会了最基础的BFS，后面，我也产生了许多问题，后面，我也慢慢理解了
我们因此要怀着不懂就问的心态，去做很多事情
在此，向致谢
代码在函数
BFS(void类型)里 ↩︎
有帮助，赞一个