【算法】BFS解决最短路径问题
📢博客主页：https://blog.ZEEKLOG.net/2301_779549673
📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！
📢本文由 JohnKi 原创，首发于 ZEEKLOG🙉
📢未来很长，值得我们全力奔赴更美好的生活✨
文章目录
📢前言
🏳️🌈一、概念
**BFS（广度优先搜索）**在图论算法中有着广泛的应用，尤其是在解决最短路径问题上表现出色。本文将详细介绍如何使用 C++ 实现 BFS 来解决最短路径问题。
广度优先搜索是一种用于图遍历的算法，它从起始节点开始，逐步探索其相邻节点，然后再探索相邻节点的相邻节点，以此类推。这种算法在解决最短路径问题时非常有用，因为它能够保证找到的路径是最短的。
在 C++ 中，可以使用队列来实现 BFS。队列的特点是先进先出，这与 BFS 的遍历方式相符合。首先，将起始节点加入队列，然后从队列中取出一个节点，探索其相邻节点，并将未访问过的相邻节点加入队列。重复这个过程，直到找到目标节点或者队列为空。
BFS 在解决各种实际问题中都有广泛的应用，比如迷宫问题、网络路由问题等。在迷宫问题中，BFS 可以用来找到从起点到终点的最短路径；在网络路由问题中，BFS 可以用来找到两个节点之间的最短路由。
接下来，我们将通过具体的代码示例来展示如何使用 C++ 实现 BFS 来解决最短路径问题。
🏳️🌈二、问题描述
以迷宫问题为例，在一张由 0 和 1 构成的图中，1 表示障碍，0 表示通路。给定起点 S 和终点 T，求从 S 到 T 的最短路长度并输出路径。
在解决这个问题时，我们可以使用广度优先搜索（BFS）算法。BFS 是一种用于图遍历的算法，它从起始节点开始，逐步探索其相邻节点，然后再探索相邻节点的相邻节点，以此类推。在迷宫问题中，我们可以将每个格子看作一个节点，相邻的格子之间有边相连。
首先，我们需要定义一个数据结构来表示迷宫。可以使用二维数组来存储迷宫的状态，其中 0 表示通路，1 表示障碍。同时，我们还需要定义一个队列来存储待探索的节点。队列的特点是先进先出，这与 BFS 的遍历方式相符合。
接下来，我们将起始节点加入队列，并标记为已访问。然后，从队列中取出一个节点，探索其相邻节点。如果相邻节点是通路且未被访问过，则将其加入队列，并标记为已访问。重复这个过程，直到找到目标节点或者队列为空。
在探索过程中，我们可以使用一个数组来记录每个节点到起始节点的距离。初始时，起始节点的距离为 0，其他节点的距离为无穷大。当探索到一个节点时，将其距离更新为上一个节点的距离加 1。这样，当找到目标节点时，我们就可以得到从起始节点到目标节点的最短路长度。
为了输出路径，我们可以在探索过程中记录每个节点的前驱节点。当找到目标节点时，从目标节点开始，沿着前驱节点回溯，直到到达起始节点，这样就可以得到从起始节点到目标节点的路径。
#include<iostream>#include<queue>constint maxn =1010;char mp[maxn][maxn];int dist[maxn][maxn];int n;int sx, sy, tx, ty;int dx[4]={1,0,0,-1}, dy[4]={0,-1,1,0};char dir[4]={'D','L','R','U'};voidbfs(){for(int i =0; i < n; i ++)for(int j =0; j < n; j ++) dist[i][j]=1e9; dist[tx][ty]=0; std::queue<std::pair<int,int>> q; std::pair<int,int> t; t.first = tx; t.second = ty; q.push(t);while(q.size()){ t = q.front(); q.pop();for(int i =0; i <4; i ++){int nx = t.first + dx[i];int ny = t.second + dy[i];if(nx >=0&& nx < n && ny >=0&& ny < n && dist[nx][ny]==1e9&& mp[nx][ny]!='1'){ dist[nx][ny]= dist[t.first][t.second]+1; q.push(std::make_pair(nx, ny));}}}}intmain(){ std::cin >> n;for(int i =0; i < n; i ++){for(int j =0; j < n; j ++){ std::cin >> mp[i][j];if(mp[i][j]=='S'){ sx = i; sy = j;}if(mp[i][j]=='T'){ tx = i; ty = j;}}}bfs(); std::cout << dist[sx][sy]<< std::endl;int x = sx, y = sy;while(x!= tx || y!= ty){for(int i =0; i <4; i ++){int nx = x + dx[i];int ny = y + dy[i];if(nx >=0&& nx < n && ny >=0&& ny < n && mp[nx][ny]!='1'){if(dist[x][y]== dist[nx][ny]+1){ std::cout << dir[i]<< std::endl; x = nx; y = ny;break;}}}}return0;}这段代码首先实现了 BFS 算法来计算从起点到终点的最短路长度，然后通过回溯找到最短路径并输出。在实际应用中，可以根据具体的问题需求对代码进行适当的调整和扩展。
🏳️🌈三、求解思路
- **BFS 特性：**BFS 是由队列实现，具有先进先出的特性。在解决最短路径问题时，队列的这种特性保证了先访问距离起点较近的节点，再逐渐扩展到距离较远的节点。就像在迷宫问题中，我们从起点开始，先探索起点周围的节点，然后再依次探索这些节点周围的节点，确保每次探索的都是距离起点最近的未访问节点。
- **求最短路长度：**从终点 T 开始倒着搜索，用一个数组 dist [][] 表示每个点到终点 T 的最短路径，如果一个点能由上一个点一步走到，则将该点入队，直到队列为空即遍历完所有的点。具体来说，我们首先将终点的距离初始化为 0，然后将终点入队。从队列中取出一个节点，遍历它的相邻节点，如果相邻节点未被访问过且不是障碍，就将其距离更新为当前节点的距离加 1，并将其入队。这样不断重复，直到队列为空，此时 dist 数组中就存储了每个点到终点的最短路径长度。
- **求路径：**在 dist 数组的基础上，从起点开始搜索，如果有一点能由当前点一步走到，则该点一定在最短路径上。我们从起点开始，遍历它的相邻节点。对于每个相邻节点，如果它能由当前节点一步走到（即相邻节点的距离等于当前节点的距离加 1），那么该相邻节点一定在最短路径上。我们将这个相邻节点加入路径中，并继续从这个节点出发进行搜索，直到到达终点。这样就可以得到从起点到终点的最短路径。
🏳️🌈四、代码实现
- 初始化：将 dist 数组初始化为无穷大，终点到终点距离设为零，用队列存储待搜索的点。
首先，我们需要定义一个二维数组 dist 来表示每个点到终点的距离。在初始化阶段，将 dist 数组中的所有元素初始化为无穷大，表示这些点到终点的距离未知。同时，将终点到终点的距离设为零，即 dist[tx][ty]=0。
然后，我们使用一个队列来存储待搜索的点。队列的特点是先进先出，这与广度优先搜索的遍历方式相符合。在 C++ 中，可以使用 std::queue 来实现队列。我们定义一个队列 q，并将终点作为初始元素加入队列中。具体代码如下：
for(int i =0; i < n; i ++)for(int j =0; j < n; j ++) dist[i][j]=1e9; dist[tx][ty]=0; std::queue<std::pair<int,int>> q; std::pair<int,int> t; t.first = tx; t.second = ty; q.push(t);- BFS 搜索：每次取出队头元素，遍历其四个方向，如果满足条件（未越界、未走过、可走），则更新该点到终点的距离并将其入队。
在 BFS 搜索阶段，我们从队列中取出队头元素，然后遍历该元素的四个方向。如果新的点满足条件（未越界、未走过、可走），则更新该点到终点的距离，并将其加入队列中。
具体来说，我们使用一个循环来遍历四个方向。对于每个方向，我们计算新的点的坐标，并检查该点是否在迷宫范围内、是否未被访问过以及是否是通路。如果满足这些条件，我们将该点的距离更新为当前点的距离加一，并将其加入队列中。代码如下：
while(q.size()){ t = q.front(); q.pop();for(int i =0; i <4; i ++){int nx = t.first + dx[i];int ny = t.second + dy[i];if(nx >=0&& nx < n && ny >=0&& ny < n && dist[nx][ny]==1e9&& mp[nx][ny]!='1'){ dist[nx][ny]= dist[t.first][t.second]+1; q.push(std::make_pair(nx, ny));}}}- 输出路径：从起点开始，根据 dist 数组判断下一个点是否在最短路径上，输出方向并更新坐标。
在输出路径阶段，我们从起点开始，根据 dist 数组判断下一个点是否在最短路径上。如果下一个点的距离等于当前点的距离加一，那么该点一定在最短路径上。
我们从起点开始，遍历它的相邻节点。对于每个相邻节点，如果它能由当前节点一步走到（即相邻节点的距离等于当前节点的距离加一），那么该相邻节点一定在最短路径上。我们将这个相邻节点加入路径中，并继续从这个节点出发进行搜索，直到到达终点。
在搜索过程中，我们可以使用一个数组来记录每个点的方向。例如，如果当前点是由上一个点向右移动得到的，那么我们可以将当前点的方向记录为 R。这样，在输出路径时，我们可以根据每个点的方向来输出路径。
具体代码如下：
int x = sx, y = sy;while(x!= tx || y!= ty){for(int i =0; i <4; i ++){int nx = x + dx[i];int ny = y + dy[i];if(nx >=0&& nx < n && ny >=0&& ny < n && mp[nx][ny]!='1'){if(dist[x][y]== dist[nx][ny]+1){ std::cout << dir[i]<< std::endl; x = nx; y = ny;break;}}}}🏳️🌈例题分析
❤️1926. 迷宫中离入口最近的出口
解题思路分析
这是一道典型的迷宫寻路问题，可以使用广度优先搜索（BFS）算法来解决。
首先，定义了迷宫的行数m、列数n，以及一个二维数组vis用于记录每个格子是否被访问过，初始化为false。还定义了四个方向数组kx和ky，分别表示上下左右四个方向的偏移量。
在nearestExit函数中，先获取迷宫的行数和列数，将入口坐标加入队列q，并标记入口已访问。然后开始进行 BFS 搜索。
每次循环，先将步数step加 1，表示进入新的一层搜索。接着遍历当前队列中的所有节点（当前层的所有可到达格子），对于每个节点，尝试向四个方向移动。
如果移动后的坐标x和y在迷宫范围内，且对应格子是空格子（maze[x][y] == '.'）且未被访问过，就判断是否到达了迷宫边界（x == 0 || x == m - 1 || y == 0 || y == n - 1），如果到达了边界，说明找到了离入口最近的出口，直接返回当
前步数step。如果没有到达边界，就将该格子坐标加入队列q，并标记为已访问。
如果队列为空，说明没有找到出口，返回 -1。
classSolution{int m, n;// 用于记录每个格子是否被访问过，初始化为falsebool vis[110][110]={false};// 表示上下左右四个方向的x偏移量int kx[4]={0,0,-1,1};// 表示上下左右四个方向的y偏移量int ky[4]={1,-1,0,0};public:intnearestExit(vector<vector<char>>& maze, vector<int>& entrance){// 获取迷宫的行数 m = maze.size();// 获取迷宫的列数 n = maze[0].size();// 定义一个队列，用于存储待探索的格子坐标 queue<pair<int,int>> q;// 将入口坐标加入队列 q.push({entrance[0], entrance[1]});// 标记入口已被访问 vis[entrance[0]][entrance[1]]=true;// 记录步数int step =0;// 当队列不为空时，进行广度优先搜索while(q.size()){// 步数加1，表示进入新的一层搜索 step++;// 获取当前层的节点数量int sz = q.size();for(int i =0; i < sz;++i){// 取出队列头部的坐标auto[a, b]= q.front(); q.pop();// 尝试向四个方向移动for(int k =0; k <4;++k){// 计算移动后的坐标int x = a + kx[k], y = b + ky[k];// 判断移动后的坐标是否在迷宫范围内，是否为空格子且未被访问过if(x >=0&& x < m && y >=0&& y < n && maze[x][y]=='.'&&!vis[x][y]){// 判断是否已经到达迷宫边界（即找到出口）if(x ==0|| x == m -1|| y ==0|| y == n -1)return step;// 将新坐标加入队列 q.push({x, y});// 标记新坐标已被访问 vis[x][y]=true;}}}}// 如果没有找到出口，返回 -1return-1;}};🧡433. 最小基因变化
这是一道求最短变换路径的问题，同样可以使用广度优先搜索（BFS）算法来解决。
首先定义了一个字符数组k，包含了基因序列中可能出现的四种字符（'A'、'C'、'G'、'T'）。
在minMutation函数中，创建了两个unordered_set容器，vis用于记录已经访问过的基因序列，hash用于存储基因库中的基因序列，通过遍历bank将基因库中的基因序列加入hash。
然后进行一系列的初始化判断，如果起始基因序列startGene和目标基因序列endGene相同，直接返回 0；如果目标基因序列不在基因库中，返回 -1。
接着将起始基因序列startGene加入队列q，并标记为已访问。开始进行 BFS 搜索，每次循环步数step加 1，表示进入新的一层搜索。
在每一层搜索中，取出队列头部的基因序列t，对于该序列的每个字符位置i（因为基因序列长度为 8），尝试将其替换为四种可能的字符k[j]（通过内层循环），得到新的基因序列tmp。
如果新序列tmp等于目标基因序列endGene，说明找到了最短变换路径，返回当前步数step。如果tmp在基因库hash中且未被访问过，就将其加入队列q，并标记为已访问。
如果队列为空，说明没有找到从startGene到endGene的变换路径，返回 -1。
classSolution{// 定义一个字符数组，包含基因序列中可能出现的四种字符char k[4]={'A','C','G','T'};public:intminMutation(string startGene, string endGene, vector<string>& bank){// 用于记录已经访问过的基因序列 unordered_set<string> vis;// 用于存储基因库中的基因序列 unordered_set<string> hash;// 将基因库中的基因序列加入hash集合for(auto e : bank) hash.insert(e);// 如果起始基因序列和目标基因序列相同，直接返回0if(startGene == endGene)return0;// 如果目标基因序列不在基因库中，返回 -1if(!hash.count(endGene))return-1;// 定义一个队列，用于存储待探索的基因序列 queue<string> q;// 将起始基因序列加入队列 q.push(startGene);// 标记起始基因序列已被访问 vis.insert(startGene);// 记录步数int step =0;// 当队列不为空时，进行广度优先搜索while(q.size()){// 步数加1，表示进入新的一层搜索++step;// 获取当前层的基因序列数量int sz = q.size();while(sz--){// 取出队列头部的基因序列 string t = q.front(); q.pop();// 遍历基因序列的每个字符位置for(int i =0; i <8;++i){// 保存当前基因序列的副本 string tmp = t;// 尝试将当前位置的字符替换为四种可能的字符for(int j =0; j <4;++j){ tmp[i]= k[j];// 如果新序列等于目标基因序列，返回当前步数if(tmp == endGene)return step;// 如果新序列在基因库中且未被访问过，将其加入队列并标记为已访问if(hash.count(tmp)&&!vis.count(tmp)) q.push(tmp), vis.insert(tmp);}}}}// 如果没有找到从起始基因序列到目标基因序列的变换路径，返回 -1return-1;}};👥总结
本篇博文对 【算法】BFS解决最短路径问题 做了一个较为详细的介绍，不知道对你有没有帮助呢
觉得博主写得还不错的三连支持下吧！会继续努力的~
