广度（宽度）优先搜索（遍历）bfs详解

简介

        广度优先搜索（遍历）是一种在图的搜索遍历中较常见的算法。它的时间复杂度通常要比深度优先搜索（遍历）要低很多，尤其是最短路。这是因为深度优先的思想是走一条路要把它走到底再去考虑别的路，如果一开始走错了，后面会浪费很多时间在死胡同上，而且递归的方法本来就需要来一次回一次。而广度优先的思想则是让每一条路都向前进发一格，那么走错路不用付出太多代价，而且这样你第一次遇到终点就是答案，因为你每条路都是同层次。层次越少，答案越好。dfs那就惨了，要弄出所有的答案进行对比。它还无需考虑递归出所以函数的return的问题。它还不会那么容易爆栈。

思想实现

        bfs基本都是用队列实现的。因为它是先进先出的。先进去的结点永远都是先搜完的。

        那队列是怎么操作的呢？别急，慢慢来。首先，我们要把起点push进队列，表示它即将搜索，并标记表示搜过的数组vis记下vis[起点]=1。然后，将起点的数据（坐标、步数、状态等）都保存在一个临时变量里，并将起点pop掉，因为它接下来搜完使命就结束了。接着，我们将所有起点（根据临时变量中的数据）能到达且合适的、没有搜过（!vis[该点]）的点都放进队列中，表示一会儿就要搜，再让vis[该点]=1，数据根据上个点按需求更改。之后每个点都像起点一样操作，不过是没有“首先”这一步骤的，因为在上个点搜索是它就设置好了。最后，如果队空，说明没有更多结点了，所以就退出。

        对于下图，我给出了它的bfs和dfs搜索顺序：

代码实现

1.模版

（代码为c++语言）

定义图

string mp[15];
/*其他数据类型也可以，一维二维三维按需求。*/

定义队列（需要加头文件<queue>）

queue<node/*某数据类型*/>Q;

vis数组

bool vis[/*大小按需填写*/]; 

定义函数

void bfs(/*起点数据*/){}

初始化起点

Q.push(/*起点数据*/);
vis[/*起点*/]=1;

中间部分

while(!Q.empty()){
	node/*队列Q的数据类型*/ temp=Q.front();
	Q.pop();
	for(/*枚举每个Q.front()能到达的点*/){
		if(vis[/*该点*/]||/*别的不合适的条件*/) continue;
		//操作
		Q.push(/*该点*/);
		vis[/*该点*/]=1; 
	}
}

2.实战练习

1.走迷宫

题目要求

        n*m的迷宫。S是起点，E是终点，#是墙壁，*是路。一段路需要1分钟行走。输出S到E的最短时间是几分钟。如果不能到达，输出-1。请使用bfs。0<n,m<=10^4

输入

        输入n和m，之后n行每行m个字符。

输出

        输出要求的数。

代码：

#include <iostream>
#include <queue>
using namespace std;
const int N=1e4+5;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};  //方向数组，为了更方便移动，迷宫中有四个方向x±1和y±1 
bool vis[N][N];
string mp[N];
struct node{
	int x;
	int y;
	int step;
};
queue<node>Q;
int bfs(int stx,int sty,int n,int m){
	Q.push({stx,sty,0});
	vis[stx][sty]=1;
	while(!Q.empty()){
		node temp=Q.front();
		Q.pop();
		for(int i=0;i<4;i++){
			int nx=temp.x+dx[i],ny=temp.y+dy[i],ns=temp.step+1;
			if(vis[nx][ny]||nx<1||ny<1||nx>n||ny>m||mp[nx][ny]=='#') continue;
			if(mp[nx][ny]=='E') return ns;
			Q.push({nx,ny,ns});
			vis[nx][ny]=1; 
		}
	} 
	return -1;
}
int main(){
	bool t=false;
	int n,m,stx,sty; cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>mp[i];
		mp[i]=' '+mp[i];  //坐标从1开始防溢出
		if(!t){
			for(int j=1;j<=m;j++){ //找起点终点 
				if(mp[i][j]=='S'){
					stx=i,sty=j;  //x在这是行y是列 
					t=true;
				}
			}	
		}
	}
	cout<<bfs(stx,sty,n,m);
	return 0;
}

不过你也能看到，编程复杂度有点高。。。

2.图的最短路

题目要求

        给出n个点m条边的无向图，告诉我从点1到其他所有点的最短路（换行隔开）。

        保证每个点都是连通的。0<n,m<10^4

输入

        首先输入n和m。然后m行输入两个数u,v，表示u和v相连。

输出

        按照题意输出。

提示：

        回想vector查看连接点的方法或查看我的这篇文章。文章https://blog.csdn.net/weixin_72829799/article/details/140257376?spm=1001.2014.3001.5501

代码：

#include <iostream>
#include <queue>
using namespace std;
const int N=1e4+5;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};  //方向数组，为了更方便移动，迷宫中有四个方向x±1和y±1 
bool vis[N];
int dis[N];
vector<int>mp[N];
queue<int>Q;
void bfs(){
	Q.push(1);
	dis[1]=0;
	vis[1]=1;
	while(!Q.empty()){
		int temp=Q.front();
		Q.pop();
		for(auto v:mp[temp]){
			if(vis[v]) continue;
			dis[v]=dis[temp]+1;
			Q.push(v);
			vis[v]=1; 
		}
	} 
}
int main(){
	int n,m; cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v; cin>>u>>v;
		mp[u].push_back(v);
		mp[v].push_back(u);
	}
	bfs();
	for(int i=2;i<=n;i++){
		cout<<dis[i]<<'\n';
	}
	return 0;
}

运行结果： 

OK，恭喜你完成所有题目！

小结

        bfs是一个运用场景广泛的算法，时间复杂度也还不错，非常实用。欢迎大家在评论区指点反馈我在文章撰写中的不足！