01、BFS与最短路径
最短路径问题是最著名的图论问题，有很多不同的场景和算法。在一种特殊的场景中，BFS也是极为优秀的最短路径算法，这种场景就是所有的相邻两个点的距离相等，一般把这个距离看作1。此时，BFS是最优的最短路径算法，查找一次从起点到终点的最短距离的计算复杂度为O(m)，m为图上边的数量，因为需要对每条边做一次检查。关于空间复杂度，用邻接表存储图的复杂度为O(n+m)，另外需要使用一个O(n)的队列，n为点的数量。
提示/
如果两点之间距离不相等，就不能用BFS了，需要用Dijkstra等通用算法。
BFS的特点是逐层扩散，也就是按最短路径扩散出去。向BFS的队列中加入邻居节点时，是按距离起点远近的顺序加入的：先加入距离起点为1的邻居节点，再加入距离为2的邻居节点，依此类推。搜索完一层，才会继续搜索下一层。一条路径是从起点开始，沿着每层逐步向外走，每多一层，路径长度就加1。那么，所有长度相同的最短路径都是从相同的层次扩散出去的。
求最短路径时，常见的问题有两个：①最短路径有多长？答案显然是唯一的；②最短路径经过了哪些点？由于最短路径可能不只一条，所以题目往往不要求输出，如果要求输出，一般是要求输出字典序最小的那条路径。
下面用一道例题介绍最短路径的计算和最短路径的打印。
例3.15迷宫
https://www.lanqiao.cn/problems/602/learning/
问题描述： 给出一个迷宫的平面图，其中标记为1 的为障碍，标记为0 的为可以通行的地方，如下所示。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上(U)、下(D)、左(L)、右(R)4个方向之一。对于上面的迷宫，从入口开始，可以按DRRURRDDDR的顺序通过迷宫，一共10 步。对于一个更复杂的迷宫(30 行50 列)，请找出一种通过迷宫的方式，其使用的步数最少。在步数最少的前提下，请找出字典序最小的一个作为答案。
注意：在字典序中D<L<R<U。
例3.15迷宫
https://www.lanqiao.cn/problems/602/learning/
问题描述： 给出一个迷宫的平面图，其中标记为1 的为障碍，标记为0 的为可以通行的地方，如下所示。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上(U)、下(D)、左(L)、右(R)4个方向之一。对于上面的迷宫，从入口开始，可以按DRRURRDDDR的顺序通过迷宫，一共10 步。对于一个更复杂的迷宫(30 行50 列)，请找出一种通过迷宫的方式，其使用的步数最少。在步数最少的前提下，请找出字典序最小的一个作为答案。
注意：在字典序中D<L<R<U。
#include<bits/stdc++.h>
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}};
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;
//(1)简单方法：
start.path="";
vis[0][0]=1; //标记起点被搜过
queue<node>q;
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;
//(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; //标记被搜过
//(1)简单方法：记录完整路径：复制上一个点的路径，加上这一步
next.path = now.path + k[i];
//(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();
}如果图上的每两个邻居节点之间的长度不同，上述普通的BFS做法就行不通了。这种一般性的最短路径算法，需要结合优先队列，具体做法请关注下一篇内容。下一篇将讲解图论的Dijkstra算法。
