当前位置：首页 > news >正文

BFS广度优先搜索详解

news 2025/7/13 5:47:19

对于BFS的，我来谈一谈自己的理解。首先，我们从一道最基础的题来进行学习:

洛谷B3625 迷宫寻路（仔细阅读哦，我就不解释了）

B3625 迷宫寻路 - 洛谷 | 计算机科学教育新生态

对于这道题以及所有的BFS题目的核心，我们的思想是这样的：

直接暴力枚举每一种情况，并把其放入队列（因为队列符合BFS算法所需要的先进先出），在枚举完这一种情况的所有符合条件的衍生情况并入队后，把这一种情况出队，枚举下一个，也就是出队后的队首元素，直至找到符合条件的答案。又或者是说，枚举完了所有情况，都没有找到正确答案，在程序运行中体现这一点的是队列为空都没有找到答案的情况。

示例：

有一个n*m的方格，里面'#'的地方是不能走的，起点是（1，1)，终点是（n，m），那么如以下图形：

.##.#
.#...
...#.

刚开始的队列（数据类型可以是pair、结构体等）：

（1，1）

想要从（1，1）走到（n，m），我们可以按刚才说的流程，把（1，1）的所有衍生坐标入队，而且入队条件为该区域不为'#'且在n*m以内。

入队后的队列：

（1，1）（2，1）

为什么只有（2，1）一个呢，这是因为对于（1，1）来说，不考虑入队条件，（1，1）确实有四种衍生情况：（0，1）（2，1）（1，2）（1，0），但其中，（0，1）（1，0）超出了n*m的范围，而（1，2）则是不能通行的'#'区域，所以最终，只有（2，1）一个符合条件的坐标被加入到了队列。可到这就完了吗？不，我们在上面说过，还需要把枚举完了所有情况的（1，1）节点出队，因为它不是答案，且没有了为答案提供价值的能力。这一点在代码里的体现不太一样，在代码中，作者是把（1，1）节点先用t保存起来，再直接出队，之后再用t代替（1，1）的作用。现在，我们就完成了一次程序将要做的枚举。之后再照着这种方式继续即可求解出答案。

全部过程展示（队列，，一行为一次枚举）：

                                                                （1，1）

                                                                （2，1）

                                                                （3，1）

                                                         （3，2）

（3，3）

（2，3）

（2，4）

（2，5）

（2，6）

因数据太水一条路拉通

代码实现：

对于程序实现上的补充：

进行一次枚举时，我们需要一个标记来表示这个路段是否走过，否则，我们的程序会在两个路

段上反复横跳。

#include<iostream>
#include<queue>
using namespace std;
int n,m;
bool temp=false;
char map[101][101];
int vis[101][101];

int dx[5]={0,0,1,-1},dy[5]={1,-1,0,0};
bool bfs(int map_x,int map_y){
   if(map_x==n&&map_y==m){
       temp=true;
   }
   if(map_x>=1&&map_x<=n&&map_y>=1&&map_y<=m){
       for(int i=0;i<4;i++){
           int xx=map_x+dx[i];
           int yy=map_y+dy[i];
           if(map[xx][yy]!='#'&&vis[xx][yy]!=1){
               vis[xx][yy]=1;
               bfs(xx,yy);
           }
       }
   }
   return temp;
}
int main(){
   cin>>n>>m;
   for(int i=1;i<=n;i++){
       for(int j=1;j<=m;j++){
           cin>>map[i][j];
       }
   }
   bool x=bfs(1,1);
   if(x){
       cout<<"Yes";
   }else{
       cout<<"No";
   }
   return 0;
}