2025年BFS算法简介

大家好，我是讯享网，很高兴认识大家。

一、算法简介

        广度优先算法（Breadth-First-Search），简称BFS。从知识点看属于图结构的搜索算法，是一种相对容易理解的简单算法。
        BFS算法从问题的初始状态（起点）出发，根据状态转换规则（图结构中的边），遍历所有可能的状态（其他节点），直到找到终结状态（终点）。因此BFS算法的复杂度和状态集合的总数密切相关。
        BFS算法虽然出自图结构，但其常用的领域却不是解决图论相关问题。一些常见的问题形式如（1）走迷宫最短路径（2）数字按规则转换的最少次数（3）棋盘上某个棋子N步后能到达的位置总数（4）病毒扩散计算（5）图像中连通块的计算。小结：BFS算法常用于求最短的步数或者求扩散性质的区域问题。

二、算法实现模板

讯享网
算法使用队列作为辅助存储结构，用于存储搜索过程中的“状态”。队列实现可采用两种方案。

（1）使用STL提供的queue类型，优点是简单易用，无需考虑存储空间问题。

（2）手写队列，优点是效率略高，且可以访问队列中任意元素（在解决某些问题时有奇效），缺点是手写不熟练时容易出错。
int qx[]，fx=0,rx=0;/< 定义队列，头尾指针fx，rx */
qx[rx++]=A;/< A入队 */
x=qx[fx++];/< 得到队头元素x，同时队头指针后移，实现出队 */

在算法处理过程中，新生成的结点（状态）要与前面所有已经产生结点比较，以免出现重复结点，陷入死循环。一般用以一个标志数组来标记某个结点是否已经处理过，而这个数组同样可以用于记录步数。具体可参见下面例题，一个标准的迷宫最短路径问题。

#include <iostream> using namespace std; char a[100][100]; int n,m,v[100][100]={0};/< v标志数组，同时也用于记录步数 */ int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; void bfs(int x,int y) { int i,j;/< 两个队列qx,qy分别存储横纵坐标 */ int qx[],qy[],fx=0,rx=0,fy=0,ry=0; qx[rx++]=1,qy[ry++]=1;/< */ v[1][1]=1;/< 迷宫起点步数记为1 */ while(fx!=rx) { x=qx[fx++],y=qy[fy++]; for(i=0;i<4;i++) { int newx=x+dx[i],newy=y+dy[i];/< bfs三要素，合法性+可访问+未标记 */ if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&a[newx][newy]=='0'&&v[newx][newy]==0) { v[newx][newy]= v[x][y]+1;/< 因为(newx,newy)是从(x,y)走一步到达，因为步数+1 */ qx[rx++]=newx,qy[ry++]=newy; } } } } int main() { ios::sync_with_stdio(0),cin.tie(0); int i,j; cin>>n>>m; for(i=1;i<=n;i++) for(j=1;j<=m;j++) cin>>a[i][j]; bfs(1,1); cout<<v[n][m]-1; return 0; }

讯享网

三、路径处理

当需要记录路径时，每生成一个子结点，就要存储指向它们父亲结点信息，此时使用的结构本质上是一个反向链式结构。以上述迷宫问题为例，定义一个数组存储(newx,newy)的父节点（x,y），反向遍历即可得到路径，反向遍历用递推实现最为容易。
全局定义一个数组 fa[100][100][2];
x=qx[fx++],y=qy[fy++];
for(i=0;i<4;i++)
{
int newx=x+dx[i],newy=y+dy[i];/< bfs三要素，合法性+可访问+未标记 */
if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&a[newx][newy]=='0'&&v[newx][newy]==0)
{
v[newx][newy]= v[x][y]+1;/< 因为(newx,newy)是从(x,y)走一步到达，因为步数+1 */
qx[rx++]=newx,qy[ry++]=newy;
fa[newx][newy][0]=x,fa[newx][newy][1]=y;/< 新增语句，记录父节点 */
}
}

新增一个函数输出路径：

讯享网void printPath(int x,int y) { if(x==0&&y==0) return; printPath(fa[x][y][0],fa[x][y][1]);/< 先递推父节点，再输出自己 */ cout<<x<<' '<<y<<endl; }

一、算法简介

二、算法实现模板

三、路径处理

相关推荐