广度优先算法（BFS）

BFS 的核心特点1、按层遍历先访问起始节点第一层然后访问所有与起始节点直接相连的节点第二层接着访问与第二层节点相连且未访问的节点第三层以此类推。2、最短路径特性在无权图中BFS 找到从起点到任意可达节点的路径一定是边数最少的路径即最短路径每条边权重视为1。3、数据结构通常使用队列queue 来实现。先入队的节点先被扩展保证了“先来先服务”的层层推进顺序。与DFS的区别BFS数据结构 队列遍历顺序 按层宽方向最短路径 无权图的最短路径空间消耗 通常较大尤其宽图典型应用 最短路径、层序遍历、连通性DFS数据结构或递归遍历顺序 沿一条路径深入再回溯最短路径 不一定得到最短路径空间消耗 通常较小尤其深图典型应用 拓扑排序、连通分量、回溯问题题目代码#includeiostream#includequeue#includevector#includealgorithmusingnamespacestd;// 搜索顺序右、下、左、上constintdirOrder[4][2]{{0,1},{1,0},{0,-1},{-1,0}};// 节点结构体表示BFS队列中的元素structNode{intx,y;// 节点坐标intsteps;// 从起点到当前节点的步数};boolBFS(constvectorvectorintmaze,intm,intn,intstartX,intstartY,intendX,intendY,intminSteps,vectorpairint,intpath){// 使用vector动态初始化访问标记数组vectorvectorboolvisited(m1,vectorbool(n1,false));// 使用vector动态初始化前驱节点数组vectorvectorintpreX(m1,vectorint(n1,-1));vectorvectorintpreY(m1,vectorint(n1,-1));queueNodeq;// 创建BFS队列q.push({startX,startY,0});// 起点入队步数为0visited[startX][startY]true;// 标记起点已访问// BFS主循环while(!q.empty()){Node curq.front();// 取出队首节点q.pop();// 到达终点if(cur.xendXcur.yendY){minStepscur.steps;// 记录最短步数// 从终点回溯重建路径intcurXendX,curYendY;while(curX!-1curY!-1){path.push_back({curX,curY});// 将当前节点加入路径inttxpreX[curX][curY];// 获取前驱节点x坐标inttypreY[curX][curY];// 获取前驱节点y坐标curXtx;// 移动到前驱节点curYty;}reverse(path.begin(),path.end());// 反转得到从起点到终点的顺序returntrue;// 找到路径返回成功}// 按顺序扩展四个方向右、下、左、上for(inti0;i4;i){intnxcur.xdirOrder[i][0];// 新节点的x坐标intnycur.ydirOrder[i][1];// 新节点的y坐标// 检查边界if(nx1nxmny1nyn){// 检查是否可通行且未访问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.steps1});// 新节点入队步数1}}}}returnfalse;// 队列为空仍未找到终点返回失败}intmain(){intm,n;cinmn;// 使用vector动态创建迷宫矩阵1-indexed多分配一行一列方便使用vectorvectorintmaze(m1,vectorint(n1,0));// 读入迷宫矩阵for(inti1;im;i){for(intj1;jn;j){cinmaze[i][j];}}// 读入起点和终点坐标intstartX,startY,endX,endY;cinstartXstartYendXendY;intminSteps-1;// 存储最短步数vectorpairint,intpath;// 存储路径坐标// 调用BFS算法if(BFS(maze,m,n,startX,startY,endX,endY,minSteps,path)){// 找到路径输出步数和路径coutminStepsendl;for(size_t i0;ipath.size();i){coutpath[i].firstpath[i].second;// 输出坐标无空格拼接if(i!path.size()-1)cout ;// 坐标之间用空格分隔}coutendl;}else{// 未找到路径输出-1cout-1endl;}return0;}总结BFS 是一种 逐层扩散 的搜索策略。需要 队列 辅助并记录 已访问 节点。在 无权图 中能保证找到 最短路径。适用于需要找最近距离或最少步骤的问题。