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

广度优先算法（BFS）

news 2026/6/30 4:01:49

BFS 的核心特点

1、按层遍历：先访问起始节点（第一层），然后访问所有与起始节点直接相连的节点（第二层），接着访问与第二层节点相连且未访问的节点（第三层），以此类推。

2、最短路径特性：在无权图中，BFS 找到从起点到任意可达节点的路径一定是边数最少的路径（即最短路径，每条边权重视为1）。

3、数据结构：通常使用队列（queue）来实现。先入队的节点先被扩展，保证了“先来先服务”的层层推进顺序。

与DFS的区别

BFS
数据结构队列
遍历顺序按层，宽方向
最短路径无权图的最短路径
空间消耗通常较大（尤其宽图）
典型应用最短路径、层序遍历、连通性
DFS
数据结构（或递归）
遍历顺序沿一条路径深入，再回溯
最短路径不一定得到最短路径
空间消耗通常较小（尤其深图）
典型应用拓扑排序、连通分量、回溯问题

题目

代码：

#include<iostream>#include<queue>#include<vector>#include<algorithm>usingnamespacestd;// 搜索顺序：右、下、左、上constintdirOrder[4][2]={{0,1},{1,0},{0,-1},{-1,0}};// 节点结构体，表示BFS队列中的元素structNode{intx,y;// 节点坐标intsteps;// 从起点到当前节点的步数};boolBFS(constvector<vector<int>>&maze,intm,intn,intstartX,intstartY,intendX,intendY,int&minSteps,vector<pair<int,int>>&path){// 使用vector动态初始化访问标记数组vector<vector<bool>>visited(m+1,vector<bool>(n+1,false));// 使用vector动态初始化前驱节点数组vector<vector<int>>preX(m+1,vector<int>(n+1,-1));vector<vector<int>>preY(m+1,vector<int>(n+1,-1));queue<Node>q;// 创建BFS队列q.push({startX,startY,0});// 起点入队，步数为0visited[startX][startY]=true;// 标记起点已访问// BFS主循环while(!q.empty()){Node cur=q.front();// 取出队首节点q.pop();// 到达终点if(cur.x==endX&&cur.y==endY){minSteps=cur.steps;// 记录最短步数// 从终点回溯重建路径intcurX=endX,curY=endY;while(curX!=-1&&curY!=-1){path.push_back({curX,curY});// 将当前节点加入路径inttx=preX[curX][curY];// 获取前驱节点x坐标intty=preY[curX][curY];// 获取前驱节点y坐标curX=tx;// 移动到前驱节点curY=ty;}reverse(path.begin(),path.end());// 反转得到从起点到终点的顺序returntrue;// 找到路径，返回成功}// 按顺序扩展四个方向：右、下、左、上for(inti=0;i<4;i++){intnx=cur.x+dirOrder[i][0];// 新节点的x坐标intny=cur.y+dirOrder[i][1];// 新节点的y坐标// 检查边界if(nx>=1&&nx<=m&&ny>=1&&ny<=n){// 检查是否可通行且未访问if(maze[nx][ny]==0&&!visited[nx][ny]){visited[nx][ny]=true;// 标记为已访问preX[nx][ny]=cur.x;// 记录前驱节点的x坐标preY[nx][ny]=cur.y;// 记录前驱节点的y坐标q.push({nx,ny,cur.steps+1});// 新节点入队，步数+1}}}}returnfalse;// 队列为空仍未找到终点，返回失败}intmain(){intm,n;cin>>m>>n;// 使用vector动态创建迷宫矩阵（1-indexed，多分配一行一列方便使用）vector<vector<int>>maze(m+1,vector<int>(n+1,0));// 读入迷宫矩阵for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){cin>>maze[i][j];}}// 读入起点和终点坐标intstartX,startY,endX,endY;cin>>startX>>startY>>endX>>endY;intminSteps=-1;// 存储最短步数vector<pair<int,int>>path;// 存储路径坐标// 调用BFS算法if(BFS(maze,m,n,startX,startY,endX,endY,minSteps,path)){// 找到路径，输出步数和路径cout<<minSteps<<endl;for(size_t i=0;i<path.size();i++){cout<<path[i].first<<path[i].second;// 输出坐标（无空格拼接）if(i!=path.size()-1)cout<<" ";// 坐标之间用空格分隔}cout<<endl;}else{// 未找到路径，输出-1cout<<-1<<endl;}return0;}