前情回顾：DFS练习-迷宫（最短路径）问题详解 一波三折 图片+文字
以及你需要会的基础：手搓数据结构之队列queue C/C++语言版（BFS算法预备知识）
一.BFS是啥
广度优先搜索（Breadth First Search）简称广搜或者 BFS，是遍历图存储结构的一种算法。BFS的原理是“逐层扩散”，从起点出发按层次先后搜索。编程时，BFS用队列(queue)实现。
基础模板为：
初始化一个队列
while(队列不为空)//当队列为空时，意味着已遍历了所有结点
{
取出队头元素
扩展队头元素
}
（别慌 耐心看下去）
二.DFS与BFS的区别
我们先用一张图感受一下DFS与BFS的搜索特点》》》
没错，dfs是“不撞南墙不回头”，而bfs是“眼观六路”。
我们用走迷宫这题形象地解释一下。
DFS相当于是一只老鼠走迷宫，“一路走到底，直到碰壁”。碰壁了回到了上一步，换个路口继续一路走到底，直到碰壁......显然，dfs的重点在于走通一条路，而不管路径的长短。
而BFS则相当于一群老鼠走迷宫，每一个路口都派一群老鼠去走。你想，一群老鼠都去走，那总有一只先到终点，这样我们就很容易找到最短的那条路，即最短路径。
三.BFS的局限性
BFS是一种很好的查找最短路径的算法，不过它只适用于一种情况：任意相邻两点之间的距离相等，一般把这个距离看作1（说白了，BFS是计算步数而不是计算距离，它会默认每两步的距离相等）如果每步之间距离不等，那就不能用bfs，而是需要用Dijkstra等通用算法。
四.重头戏：BFS迷宫图文详解
迷宫如图所示，阴影部分表示不能走。起点标记为1
根据以下图片及文字体会搜索的过程 我们规定走的顺序为左—上—右—下
①这群老鼠从起点1出发
②1有两个邻居，2和3，派出两群老鼠分别走。这时距离起点1一步之远的2，3都走到了。
③向2，3的邻居走。我们按顺序先走2的所有邻居4，5，6。
④向3的邻居7，8走。这时距离起点1两步之远的点（45678）都走到了。而且遇到了终点8，两步便是最短路径。
⑤不过这群老鼠还是决定把所有的点都走到。向4的邻居9，5的邻居10，6的邻居11，7的邻居12，13走。
⑥继续向10的邻居14，11的邻居15走。此时所有点都走到了。while循环停止。
五.代码实现
1.为啥用队列
对于 BFS 算法，我们需要一层一层遍历所有的相邻结点。那么相邻结点之间的先后顺序如何确定？因此我们需要一个数据结构来进行存储和操作，使得先遍历的结点先被存储，直到当前层都被存储后，按照先后顺序，先被存储的结点也会被先取出来，继续遍历它的相邻结点。因此我们可以发现，这个需求不就是我们的队列吗？
对于迷宫这个问题也可以给你很形象的解释，离终点1，2，3......步的位置可以形成一个队列，在这个队列中，对于每一个位置它可以再去寻找下一个位置，那么当走到下一个位置，我把上一步就可以忘了，这是不是就符合先进先出，后来的接上？
2.既然要遍历了所有结点，那怎么保证我知道最短的步数。
我们可以设置一个距离数组，存储每个位置离起点的步数，并且这个数组也可以用来判断这个位置是否被走到了。怎么做？我们先把所有位置都初始化为-1，如果这个位置被走到了，-1就改为这个位置离起点的步数。有一点很巧妙，即使在第一只老鼠已经到达了终点的情况下，程序虽然没有终止，但是其他老鼠也不会走到终点了，因为距离数组中的终点位置已不再是-1，而是最短步数了！
3.补充知识：pair用法
对于一个迷宫，每个位置都有其x,y坐标，那么能否做到用一个数组就能把每一个位置对应的坐标存下来？当然可以！我们可以使用pair。
基本用法为：
pair<数据类型，数据类型> 名字(元素1，元素2);
访问两个元素操作可以通过first和sencond访问。就跟结构体一样，详情看代码。
我们可以用typedef实现简化声明的目的。
简单看一下题目，该题比我讲解的版本更简单一些，已经规定好了起点和终点。
直接上代码，注意看注释喔—>
#include <iostream>
using namespace std;
typedef pair<int, int> PII;//存坐标
const int N = 105;
int n, m;
int maze[N][N];//存地图
int dist[N][N];//存每一位置到起点的步数 distance
PII queue[N * N];//存每个位置的坐标的数组，只不过数组里的每个元素是个坐标
int bfs()
{
int head = 0; int tail = 0;
queue[0] = { 0,0 };//注意用的大括号
memset(dist, -1, sizeof(dist));//设置为-1表示这格没走过
dist[0][0] = 0;
int dx[4] = { -1,0,1,0 };//顺序为左上右下的方向数组
int dy[4] = { 0,1,0,-1 };
while (head <= tail)//当队头不为空时
{
PII t = queue[head++];//把队头取出来并弹出该队头
for (int i = 0; i < 4; i++)
{
int x = t.first + dx[i];
int y = t.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m && maze[x][y] == 0
&& dist[x][y] == -1)//就是判断是否越界已经是否能走
{
dist[x][y] = dist[t.first][t.second] + 1;
tail++;
queue[tail] = { x,y };
}
}
}
return dist[n - 1][m - 1];
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
scanf("%d", &maze[i][j]);
}
}
printf("%d\n", bfs());
return 0;
}呼~这篇文章就到这里结束啦，有任何问题欢迎在评论区提问。你的点赞关注收藏就是对我最大的支持，未来我也会继续创作更多优质文章！文章来源：https://www.toymoban.com/news/detail-835202.html
文章来源地址https://www.toymoban.com/news/detail-835202.html
到了这里，关于BFS算法(宽度优先搜索)超强解析 BFS迷宫问题图文详解 DFS与BFS的区别的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
