【算法】BFS解决最短路径问题
📢博客主页：https://blog.csdn.net/2301_779549673
📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！
📢本文由 JohnKi 原创，首发于 CSDN🙉
📢未来很长，值得我们全力奔赴更美好的生活✨
文章目录
- 📢前言
- 🏳️🌈一、概念
- 🏳️🌈二、问题描述
- 🏳️🌈三、求解思路
- 🏳️🌈四、代码实现
- 🏳️🌈例题分析
- ❤️1926. 迷宫中离入口最近的出口
- 🧡433. 最小基因变化
- 👥总结
📢前言
🏳️🌈一、概念
**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>
const int 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'};
void bfs() {
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));
}
}
}
}
int main() {
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;
}
}
}
}
return 0;
}
这段代码首先实现了 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. 迷宫中离入口最近的出口
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。
class Solution {
int m, n;
// 用于记录每个格子是否被访问过，初始化为false
bool vis[110][110] = {false};
// 表示上下左右四个方向的x偏移量
int kx[4] = {0, 0, -1, 1};
// 表示上下左右四个方向的y偏移量
int ky[4] = {1, -1, 0, 0};
public:
int nearestExit(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;
}
}
}
}
// 如果没有找到出口，返回 -1
return -1;
}
};
🧡433. 最小基因变化
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。
class Solution {
// 定义一个字符数组，包含基因序列中可能出现的四种字符
char k[4] = {'A', 'C', 'G', 'T'};
public:
int minMutation(string startGene, string endGene, vector<string>& bank) {
// 用于记录已经访问过的基因序列
unordered_set<string> vis;
// 用于存储基因库中的基因序列
unordered_set<string> hash;
// 将基因库中的基因序列加入hash集合
for (auto e : bank)
hash.insert(e);
// 如果起始基因序列和目标基因序列相同，直接返回0
if (startGene == endGene)
return 0;
// 如果目标基因序列不在基因库中，返回 -1
if (!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);
}
}
}
}
// 如果没有找到从起始基因序列到目标基因序列的变换路径，返回 -1
return -1;
}
};
👥总结
本篇博文对 【算法】BFS解决最短路径问题 做了一个较为详细的介绍，不知道对你有没有帮助呢
觉得博主写得还不错的三连支持下吧！会继续努力的~
