图论|BFS最短路径的两种打印方法图论|算法

预告：我用两年写的新书《算法竞赛》，已于2022年2月交给清华大学出版社，预计于2022年7月出版。
《算法竞赛》是一本“大全”，内容覆盖“基础-中级-高级”，篇幅700页左右。部分知识点的草稿已经在本博客发表。
本篇博客节选自新书《算法竞赛》的“3.4 BFS与最短路”。

文章目录

1、BFS求最短路
2、路径打印的简单方法
3、路径打印的标准方法

1、BFS求最短路 【图论|BFS最短路径的两种打印方法】?? 最短路问题是最有名的图论问题，有很多不同的场景和算法。
?? 在一种特殊的场景中，BFS也是极为优秀的最短路算法，这种场景就是：所有的相邻两个点的距离相等，一般把这个距离看成1。此时BFS是最优的最短路径算法，查找一次从起点到终点的最短距离的计算复杂度是O(m) ，m是图上边的数量，因为需要对每条边做一次检查。
?? 如果两点之间距离不相等，就不能用BFS了，需要用Dijkstra等通用算法。
?? BFS的特点是逐层扩散，也就是按最短路扩散出去。往BFS的队列中加入邻居结点时，是按距离起点远近的顺序加入的：先加入距离起点为1的邻居结点，加完之后，再加入距离为2的邻居结点，等等。搜完一层，才会继续搜下一层。一条路径是从起点开始，沿着每一层逐步往外走，每多一层，路径长度就增加1。那么，所有长度相同的最短路径都是从相同的层次扩散出去的。
?? 求最短路径时，常见的问题有两个：
?? （1）最短路径有多长？答案显然是唯一的；
?? （2）最短路径经过了哪些点？由于最短路径可能不只一条，所以题目往往不要求输出，如果要求输出，一般是要求输出字典序最小的那条路径。
?? 下面用一道例题介绍最短路径的计算和最短路径的打印。
2019年省赛真题迷宫 https://www.lanqiao.cn/problems/602/learning/
题目描述：下图给出了一个迷宫的平面图，其中标记为1 的为障碍，标记为0 的为可以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上、下、左、右四个方向之一。对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，一共10 步。其中D、U、L、R 分别表示向下、向上、向左、向右走。对于下面这个更复杂的迷宫（30 行50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中D ??本题是基本的BFS搜索最短路。BFS是最优的算法，每个点只需搜一次，即进队列和出队列各一次。
??题目要求返回字典序最小的最短路径，那么只要在每次扩散下一层（往BFS的队列中加入下一层的结点）时，都按字典序“D ??本题的关键是路径打印，下面给出两种打印方法。
2、路径打印的简单方法 ??简单方法，适合小图。
??每扩展到一个点v，都在v上存储从起点s到v的完整路径path。到达终点t时，就得到了从起点s到t的完整路径。
??在下面的代码中，在每个结点上记录从起点到这个点的路径。到达终点后，用cout< ??这样做的缺点是会占用大量空间，因为每个点上都存储了完整的路径。

#include using namespace std; struct node{ int x; int y; //(1)简单方法： string path; //path,记录从起点(0,0)到这个点(x,y)的完整路径 }; char mp[31][51]; //用矩阵存地图 char k[4]={'D','L','R','U'}; //字典序 int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}}; //4个方向 int vis[30][50]; //标记。vis=1: 已经搜过，不用再搜void bfs(){ node start; start.x=0; start.y=0; //(1)简单方法： start.path=""; vis[0][0]=1; //标记起点被搜过 queueq; q.push(start); //把第一个点放进队列，开始BFS while(!q.empty()){ node now = q.front(); //取出队首 q.pop(); if(now.x==29 && now.y==49){ //第一次达到终点，这就是字典序最小的最短路径 //(1)简单方法：打印完整路径 cout << now.path << endl; return; } for(int i=0; i<4; i++){//BFS：扩散邻居结点 node next; next.x = now.x + dir[i][0]; next.y = now.y + dir[i][1]; if(next.x<0||next.x>=30||next.y<0||next.y>=50)//越界了 continue; if(vis[next.x][next.y]==1 || mp[next.x][next.y]=='1') continue; //vis=1:已经搜过; mp=1:是障碍 vis[next.x][next.y]=1; //标记被搜过 //(1)简单方法：记录完整路径：复制上一个点的路径，加上这一步 next.path = now.path + k[i]; q.push(next); } } } int main(){ for(int i=0; i<30; i++) cin >> mp[i]; //读题目给的地图数据 bfs(); }

3、路径打印的标准方法 ??标准方法，适合大图。
??其实不用在每个结点上存储完整路径，而是在每个点上记录它的前驱结点就够了，这样从终点能一步步回溯到起点，得到一条完整路径。称这种路径记录方法为“标准方法”。
??注意看代码中的print_path()，它是递归函数，先递归再打印。从终点开始，回溯到起点后，再按从起点到终点的顺序，正序打印出完整路径。

#include using namespace std; struct node{ int x; int y; }; char mp[31][51]; //存地图 char k[4]={'D','L','R','U'}; //字典序 int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}}; int vis[30][50]; //标记。vis=1: 已经搜过，不用再搜//(2)标准方法： char pre[31][51]; //用于查找前驱点。例如pre[x][y] = ‘D’，表示上一个点 //往下走一步到了(x,y)，那么上一个点是(x-1,y) void print_path(int x,int y){//打印路径：从(0,0)到(29,49) if(x==0 && y==0)return; //回溯到了起点，递归结束，返回 if(pre[x][y]=='D')print_path(x-1,y); //回溯，往上 U if(pre[x][y]=='L')print_path(x,y+1); //回溯，往右 R if(pre[x][y]=='R')print_path(x,y-1); if(pre[x][y]=='U')print_path(x+1,y); printf("%c",pre[x][y]); //最后打印的是终点 } void bfs(){ node start; start.x=0; start.y=0; vis[0][0]=1; //标记起点被搜过 queueq; q.push(start); //把第一个点放进队列，开始BFS while(!q.empty()){ node now = q.front(); //取出队首 q.pop(); if(now.x==29 && now.y==49){ //第一次达到终点，这就是字典序最小的最短路径 //(2)标准方法：打印完整路径，从终点回溯到起点，打印出来是从起点到终点的正序 print_path(29,49); return; } for(int i=0; i<4; i++){//扩散邻居结点 node next; next.x = now.x + dir[i][0]; next.y = now.y + dir[i][1]; if(next.x<0||next.x>=30||next.y<0||next.y>=50)//越界了 continue; if(vis[next.x][next.y]==1 || mp[next.x][next.y]=='1') continue; //vis=1:已经搜过; mp=1:是障碍 vis[next.x][next.y]=1; //标记被搜过 //(2)标准方法：记录点(x,y)的前驱 pre[next.x][next.y] = k[i]; q.push(next); } } } int main(){ for(int i=0; i<30; i++) cin >> mp[i]; //读题目给的地图数据 bfs(); }