#创作计划#广（宽）度优先搜索精讲

蒟蒻 · 徐奕辰

2025-08-13 17:30:08

发布于：北京

38阅读

0回复

0点赞

广度优先搜索精讲

什么是广度优先搜索？

广度优先搜索（英文:Breadth First Search，简称 bfs），又称宽度优先搜索，是一种搜索算法。顾名思义，就是更大范围内搜索，先访问完当前顶点的所有邻接点，然后再访问下一层的所有节点，该算法适用于解决最短、最小路径等问题。

广度优先搜索使用队列实现，每次将周围的邻接点加入队列，逐层搜索。

广度优先搜索因为其采用层级遍历，像洪水一样逐层扩散，无需重复访问、无需回溯，所以较深度优先搜索的指数级时间复杂度的效率有着显著提升。

广度优先搜索的原理和实现

广度优先搜索的步骤

广度优先搜索通过队列实现，将起始点加入队列，然后只要队列不为空，对于合法的邻接点加入队列，一层一层的进行遍历。

例如对于一个无向图，有 $(1,2)$ , $(1,3)$ , $(3,4)$ , $(2,4)$ 四条边。广度优先搜索的步骤如下：

定义一个队列 $q$ ，用于维护当前待处理的节点；
从 $1$ 开始搜索，将 $1$ 节点加入队列 $q$ ；
$1$ 的邻接边有 $(1,2)$ 和 $(1,3)$ ，然后将节点 $2$ 和 $3$ 加入队列 $q$ ，将节点 $1$ 退出队列；
然后对于节点 $2$ ，它的邻接边有 $(1,2)$ 和 $(2,4)$ ，因为节点 $1$ 已被访问过，跳过，将节点 $4$ 加入队列 $q$ ，将节点 $2$ 退出队列；
对于节点 $3$ ，它的邻接边有 $(1,3)$ 和 $(3,4)$ ，但是节点 $1$ 和 $4$ 都已被访问，跳过；
对于节点 $4$ ，它的邻接边有 $(2,4)$ 和 $(3,4)$ ，但是节点 $2$ 和 $3$ 都已被访问过，跳过；
队列空了，遍历结束。

广度优先搜索模版代码

/*                     bfs模版                   */ 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10; //以邻接表存图为示例
int n,m;//节点数，边数 
vector<int> g[N];
bool vis[N];//记录节点是否访问过
/*    记录遍历节点    */ 
struct node{
    int id;//当前访问到的节点编号
    int step;//当前路径的长度
};
/*     广度优先搜索主体代码   */ 
int bfs(int sx,int ex){//sx表示开始节点，ex表示终点
    queue<node> q; //队列q维护遍历节点
	q.push({sx,0}) //将起点加入队列，长度为0
	vis[sx] = 1; //起点已被访问
	while(!q.empty()){//队列不为空 
		node now = q.front(); //取出最前面的节点遍历
		q.pop(); //记得及时退队列
		if(now.id == ex){//当遍历到了终点 
			return now.step; //当前路径长度 
		} 
		for(auto &it : g[now.id]){ //遍历邻接边 
			if(!vis[it]){
				q.push({it,now.step+1});//入队列 
				vis[it] = 1;//标记已被遍历 
			}
		}
	}
	return -1;// 没搜到终点 
}
/*             主函数部分    */
int main(){
	cin >> n >> m;
	for(int i = 1;i <= m;i ++){
		int u,v;
		cin >> u >> v;
		g[u].push_back(v);//存储邻接表 
		g[v].push_back(u);
	}
	cout << bfs(1,n);//搜索
	return 0; 
}

题目练习

迷宫类问题

A8036.走迷宫

这道题是一个经典的迷宫问题，相对与用 dfs 算法，bfs 算法效率更高。
这道题中，角色要在 $n \times m$ 的地图里走路，每次只能向上下左右走 $1$ 格，并且只有.的位置才能走。
对于这类题型，我们可以用 dx 和 dy数组记录运动轨迹，每次遍历 dx ， dy 数组，移动到对应位置。
注意：对于走迷宫类题型需要注意当前位置是否合法，即是否满足当前位置不越界，当前位置可以走。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n,m;//地图长宽
char mp[N][N];//地图
bool vis[N][N];
int dx[] = {-1,1,0,0},dy[] = {0,0,-1,1}; //运动轨迹
struct node{
    int x,y;//坐标
    int step;//路径长度
};
int bfs(int sx,int sy,int ex,int ey){
    queue<node> q;//队列
    q.push({sx,sy,0});//加入起始点
    vis[sx][sy] = 1;//标记起始位置
    while(!q.empty()){//不为空
        node now = q.front();//最前面的
        q.pop();//退队列
        if(now.x == ex && now.y == ey) return now.step;
        for(int i = 0;i < 4;i ++){
            int nx = now.x + dx[i],ny = now.y + dy[i];//当前位置
            if(nx < 1|| nx > n || ny < 1 || ny > m) continue;//越界
            if(mp[nx][ny] == '#' || vis[nx][ny]) continue;//不能走
            q.push({nx,ny,now.step+1});//入队列
            vis[nx][ny] = 1;//标记
        }
    }
    return -1;
}
int main(){
    cin>> n >> m;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            cin >> mp[i][j];
    cout << bfs(1,1,n,m) + 1;//加上起始点
}

预期分数： $100pts$
时间复杂度： $\operatorname{O(nm)}$
空间复杂度： $\operatorname{O(nm)}$

连通块问题

A8040.细胞

本题目是一道经典的连通块问题。
这道题具有一定思维含量，可以通过循环遍历，对于每个不属于其他连通块的格子（ $vis_{i,j}$ $=$ $0$ ）通过 bfs 搜索确定大小并标记所属的格子，最后记录有多少个连通块。
代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n,m;
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};//运动轨迹
struct node{
    int x;
    int y;
};//因为不是最短路，所以不需要step
bool vis[N][N];
char mp[N][N];
void bfs(int sx,int sy){
    queue<node> q;
    q.push({sx,sy});//起始点入队
    vis[sx][sy] = 1;
    while(!q.empty()){
        node now = q.front();
        q.pop();
        for(int i = 0;i < 4;i ++){
            int nx = now.x + dx[i],ny = now.y + dy[i];//当前位置
            if(vis[nx][ny]) continue;
            if(mp[nx][ny] == '0') continue;//为 0 跳过
            if(nx < 1 || ny < 1 || nx > n || ny > m) continue;
            vis[nx][ny] = 1;
            q.push({nx,ny});
        }
    }
}
int main(){
    int ans = 0;
    cin >> n >> m;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            cin >> mp[i][j];
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            if(vis[i][j] == 0 && mp[i][j] !='0'){//是否为一块新的细胞
                ans ++;
                bfs(i,j);//跑bfs把这整块细胞标记
            }
        }
    }
    cout << ans;
}