#创作计划# 广度优先搜索 BFS

Xclipse

2025-07-09 19:17:37

发布于：上海

10阅读

0回复

0点赞

广度优先搜索 Breadth First Search

引言

搜索算法一直是各类计算机赛事考察的焦点，在各大刷题网站上有着巨大存量。关于深度优先搜索，请查看@Macw07的文章 DFS.
本文主要聚焦于另一种常见的搜索算法——广度优先搜索（下文简称“广搜”）。请确认在开始学习广度优先搜索前你已经掌握 队列queue 这一基本数据结构，因为广搜的操作基于队列先进先出的特点，相应的，深度优先搜索可以对应 栈stack 这一数据结构。广搜主要应用于解决迷宫问题、图形连通性问题以及在树和图形结构中查找z最短路径等问题。

在开始之前，你可能会发现，广搜的应用场景与深搜深度重合，那么学习他的意义在哪里呢？对于一个的 $n*m$ 地图来说，广搜的时间复杂度为 $O(n*m)$ ，而深搜的时间复杂度是比广搜大的（虽然我不知道确切值），我们可以从一道模板题中得出结论走迷宫

这是广搜的结果，平平无奇全AC：

而这是深搜的结果，出现了几个蓝不拉几的东西：

也许是因为我个人技艺不佳，但不可否认的是广搜在最短路一类问题上对深搜是降维打击。广搜的实现类似于水波扩散，具体流程通过queue先进先出的逻辑对地图进行遍历，从始结点开始，寻找一步到达的合法可行点（可能存在其他条件限制），并加入队列，然后弹出始结点，由依次对队列中的结点执行寻找操作，直至队列为空，这样能确保到达终点时“步数”一定是最小的。具体的可视化逻辑参见这里。

详细操作

本文将以下图为例，对bfs的算法进行具体分析：
要求：从根节点开始，以广度优先搜索的方式找到节点G（其实这张图深搜来的更快）

第一步

取出根节点，遍历所有可达的节点并将其压入队列，弹出根节点。广搜的遍历顺序就是队列的顺序，一般情况下，这个节点可访达的节点 的顺序取决于你，邻接表、邻接矩阵、二维数组中的dx，dy数组都是如此。

这里其实省略了把根节点压入队列并弹出这一步的具象化。

第二步（while循环体）

取出队首元素，弹出，重复直到队列为空。

没了。。。广搜的核心到此为止，逻辑其实很容易理解。

示例题目

A8036.走迷宫
非常标准的bfs模板题，与前文的树不同，这是一道地图题，但是逻辑还是一样的。

存图，使用二维数组 char mp[43][43]；完成存储（这是非常基本的东西了）。在绝大多数的搜索题目中还需要一个 vis数组，用来标记节点是否访问过，以免进入死循环。同时，我采用结构体存储一个点，用于bfs函数中的队列。

struct pt{int x,y,step;}l,r;
queue<pt>q;
char mp[43][43]; bool vis[43][43];//vis也可以用int
int main(){
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin>>mp[i][j];
        }
    }
    return 0;
}

构建主体函数循环体，上面的图片中也提到，bfs用的是 while 循环。出现check函数与dir二维数组在各题中基本是通用的。

while(q.size()){
        r=q.front();
        q.pop();
        for(int i=0; i<4; i++){
            if(r.x==n&&r.y==m){cout<<r.step; break;}
            l.x=r.x+dir[i][0],l.y=r.y+dir[i][1];
            l.step=r.step+1;
            if(check(l)){
                vis[l.x][l.y]=1;
                q.push(l);
            }
        }
    }

完整代码构建，具体见注释，如有不懂欢迎私信。

#include<iostream>
#include<queue>
using namespace std;         //基本东西
char mp[43][43];
bool vis[43][43];            //前文的二维数组
struct pt{int x,y,step;}l,r; //结构体存点
int n,m,count;
int dir[4][2]={-1,0,0,1,1,0,0,-1};   
//方向导向数组，dir[n][0]表示x方向，如果你不确定自己搞不搞得明白，请将x方向与y方向分开！
bool check(pt p){
	if(p.x<1 || p.x>n+1 || p.y<1 || p.y>m+1){return 0;}     //是否越界
	if(vis[p.x][p.y]){return 0;}                            //是否被访问
	if(mp[p.x][p.y]!='.'){return 0;}                        //是否有障碍
	return 1;
}
void bfs(int x,int y){       //核心部分
    queue<pt>q;
    q.push({x,y,1});
    vis[x][y]=1;
    while(q.size()){
        r=q.front();
        q.pop();
        for(int i=0; i<4; i++){
            if(r.x==n&&r.y==m){cout<<r.step; break;}
            l.x=r.x+dir[i][0],l.y=r.y+dir[i][1];
            l.step=r.step+1;
            if(check(l)){
                vis[l.x][l.y]=1;
                q.push(l);
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin>>mp[i][j];
        }
    }
    bfs(1,1);
    return 0;
}

拓展：邻接表与邻接矩阵

邻接表与邻接矩阵是两种用于存储节点间通路的数据结构，大部分运用于最短路等问题，然而，遇到像算法分析那样的题目，我们依旧可以使用bfs+邻接表/矩阵完成，以下展示代码

struct edge{int u,v,w};           //邻接表，u为起始节点，v为终点，w为带权边的权重
vector<edge> egs[10000]; 
//你的其它代码
int u,v,w; cin>>u>>v>>w; egs[u].push_back({u,v,w}); //存边，无向边就反过来在存一遍

本质上，迪杰斯特拉算法就是bfs的一种体现，参照本题单源最短路径。如果各位有兴趣，可以站内搜索相关帖子或 @我来出一篇关于最短路算法的文章。
希望各位点个赞，谢谢。

有帮助，赞一个