欢迎拜访：雾里看山-CSDN博客
本篇主题：算法思想之 BFS 解决 最短路问题
发布时间：2025.7.30
隶属专栏：算法
目录
算法介绍
BFS（广度优先搜索）通过 “逐层扩散” 的方式遍历图中节点，这种特性使其在无权图或边权相等的图中，能天然找到从起点到目标节点的最短路径。其核心逻辑在于：越早被访问到的节点，距离起点越近。当首次抵达目标节点时，所经过的路径必然是边数最少的最短路径。
算法适用场景
- 无权图的最短路径计算（如社交网络中两人的最短好友链）
- 边权值均为 1 的图（如网格中移动一步的代价固定）
- 迷宫类问题（从起点到终点的最少步数）
- 层次化结构的遍历（如二叉树的最小深度）
实现步骤与关键要素
- 图的表示方式
- 邻接表：适用于稀疏图，用
vector<vector<int>>存储每个节点的邻接节点 - 邻接矩阵：适用于稠密图，用二维数组
graph[i][j]表示节点 i 与 j 是否相连 - 网格结构：用二维数组表示，通过方向数组遍历相邻单元格
- 邻接表：适用于稀疏图，用
- 核心数据结构
- 队列（
queue）：存储待访问的节点，保证按层次顺序处理 - 距离记录（
dist）：数组或矩阵，记录起点到各节点的最短距离，初始化为- 1（未访问） - 前驱节点（
prev）：可选，用于回溯还原完整路径
- 队列（
- 算法执行流程
- 初始化：起点入队，距离设为
0 - 循环处理：
- 取出队首节点
u，遍历其所有邻接节点v - 若
v未访问（dist [v] = -1），则设置dist [v] = dist [u] + 1，记录前驱prev [v] = u，将v入队 - 若
v是目标节点，可提前退出循环
- 取出队首节点
- 结果：
dist [目标节点]即为最短距离，通过prev数组可还原路径
- 初始化：起点入队，距离设为
例题
迷宫中离入口最近的出口
题目链接
题目描述
给你一个
m x n的迷宫矩阵maze（下标从0开始），矩阵中有空格子（用'.'表示）和墙（用'+'表示）。同时给你迷宫的入口entrance，用entrance = [entrancerow, entrancecol]表示你一开始所在格子的行和列。
每一步操作，你可以往 上， 下， 左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离entrance最近 的出口。出口 的含义是maze边界 上的 空格子。entrance格子 不算 出口。
请你返回从entrance到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回-1。
示例 1：
输入：maze = [[“+”,“+”,“.”,“+”],[“.”,“.”,“.”,“+”],[“+”,“+”,“+”,“.”]], entrance = [1,2]
输出：1
解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。
一开始，你在入口格子 (1,2) 处。
你可以往左移动 2 步到达 (1,0) 。
你可以往上移动 1 步到达 (0,2) 。
从入口处没法到达 (2,3) 。
所以，最近的出口是 (0,2) ，距离为 1 步。示例 2：
输入：maze = [[“+”,“+”,“+”],[“.”,“.”,“.”],[“+”,“+”,“+”]], entrance = [1,0]
输出：2
解释：迷宫中只有 1 个出口，在 (1,2) 处。
(1,0) 不算出口，因为它是入口格子。
初始时，你在入口与格子 (1,0) 处。
你可以往右移动 2 步到达 (1,2) 处。
所以，最近的出口为 (1,2) ，距离为 2 步。示例 3：
输入：maze = [[“.”,“+”]], entrance = [0,0]
输出：-1
解释：这个迷宫中没有出口。提示：
maze.length == mmaze[i].length == n1 <= m, n <= 100maze[i][j]要么是'.'，要么是'+' 。entrance.length == 20 <= entrancerow < m0 <= entrancecol < nentrance 一定是空格子。
算法思路
利用层序遍历来解决迷宫问题，是最经典的做法。
我们可以从起点开始层序遍历，并且在遍历的过程中记录当前遍历的层数。这样就能在找到出口的时候，得到起点到出口的最短距离
代码实现
class Solution {
typedef pair<int, int> PII;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};
public:
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int m = maze.size();
int n = maze[0].size();
bool vis[101][101];
memset(vis,0, sizeof(vis));
queue<PII> q;
q.push({entrance[0], entrance[1]});
vis[entrance[0]][entrance[1]] = true;
int ret = 0;
while(q.size())
{
ret++;
int k = q.size();
while(k--)
{
auto [a,b] = q.front();
q.pop();
for(int i = 0; i < 4; i++)
{
int x = a+dx[i],y = b+dy[i];
if(x>=0 && x<m && y>=0 && y<n && maze[x][y] == '.' &&vis[x][y] == false)
{
if(x == 0 || y == 0 || x == m-1 || y == n-1)
return ret;
vis[x][y] = true;
q.push({x,y});
}
}
}
}
return -1;
}
};
最小基因变化
题目链接
题目描述
基因序列可以表示为一条由
8个字符组成的字符串，其中每个字符都是'A'、'C'、'G'和'T'之一。
假设我们需要调查从基因序列start变为end所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
- 例如，
"AACCGGTT" --> "AACCGGTA"就是一次基因变化。
另有一个基因库bank记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库bank中）
给你两个基因序列start和end，以及一个基因库bank，请你找出并返回能够使start变化为end所需的最少变化次数。如果无法完成此基因变化，返回-1。
注意：起始基因序列start默认是有效的，但是它并不一定会出现在基因库中。
示例 1：输入：start = “AACCGGTT”, end = “AACCGGTA”, bank = [“AACCGGTA”]
输出：1示例 2：
输入：start = “AACCGGTT”, end = “AAACGGTA”, bank = [“AACCGGTA”,“AACCGCTA”,“AAACGGTA”]
输出：2示例 3：
输入：start = “AAAAACCC”, end = “AACCCCCC”, bank = [“AAAACCCC”,“AAACCCCC”,“AACCCCCC”]
输出：3提示：
start.length == 8end.length == 80 <= bank.length <= 10bank[i].length == 8start、end和bank[i]仅由字符['A', 'C', 'G', 'T']组成
算法思路
如果将每次字符串的变换抽象成图中的两个顶点和一条边的话，问题就变成了 边权为 1的最短路问题。
因此，从起始的字符串开始，来一次 bfs 即可。
代码实现
class Solution {
public:
int minMutation(string startGene, string endGene, vector<string>& bank) {
unordered_set<string> hash(bank.begin(), bank.end());
unordered_set<string> vis;
if(startGene == endGene)
return 0;
if(!hash.count(endGene))
return -1;
string change = "ACTG";
queue<string> q;
q.push(startGene);
vis.insert(startGene);
int ret = 0;
while(q.size())
{
ret++;
int k = q.size();
while(k--)
{
string tmp = q.front();
q.pop();
for(int i = 0; i < 8; i++)
{
string t = tmp;
for(int j = 0; j < 4; j++)
{
t[i] = change[j];
if(hash.count(t) && !vis.count(t))
{
if(t == endGene)
return ret;
q.push(t);
vis.insert(t);
}
}
}
}
}
return -1;
}
};
单词接龙
题目链接
题目描述
字典
wordList中从单词beginWord到endWord的 转换序列 是一个按下述规格形成的序列beginWord -> s1 -> s2 -> ... -> sk：
- 每一对相邻的单词只差一个字母。
- 对于
1 <= i <= k时，每个si都在wordList中。注意，beginWord不需要在wordList中。sk == endWord
给你两个单词beginWord和endWord和一个字典wordList，返回 从beginWord到endWord的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回0。
示例 1：输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出：5
解释：一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。示例 2：
输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出：0
解释：endWord “cog” 不在字典中，所以无法进行转换。提示：
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord、endWord和wordList[i]由小写英文字母组成beginWord != endWordwordList中的所有字符串 互不相同
算法思路
此题的算法思路和上一题一样！
代码实现
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> hash(wordList.begin(), wordList.end());
unordered_set<string> vis;
if(!hash.count(endWord)) return 0;
int n = endWord.size();
string change = "abcdefghijklmnopqrstuvwxyz";
queue<string> q;
q.push(beginWord);
if(hash.count(beginWord))
vis.insert(beginWord);
int ret = 1;
while(q.size())
{
ret++;
int k = q.size();
while(k--)
{
string tmp = q.front();
q.pop();
for(int i = 0; i < n; i++)
{
string t = tmp;
for(int j = 0; j < 26; j++)
{
t[i] = change[j];
if(hash.count(t) && !vis.count(t))
{
if(t == endWord)
return ret;
q.push(t);
vis.insert(t);
}
}
}
}
}
return 0;
}
};
为高尔夫比赛砍树
题目链接
题目描述
你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个
m x n的矩阵表示， 在这个矩阵中：
0表示障碍，无法触碰1表示地面，可以行走比 1 大的数表示有树的单元格，可以行走，数值表示树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为1（即变为地面）。
你将从(0, 0)点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回-1。
可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
示例 1：
输入：forest = [[1,2,3],[0,0,4],[7,6,5]]
输出：6
解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。示例 2：
输入：forest = [[1,2,3],[0,0,0],[7,6,5]]
输出：-1
解释：由于中间一行被障碍阻塞，无法访问最下面一行中的树。示例 3：
输入：forest = [[2,3,4],[0,0,5],[8,7,6]]
输出：6
解释：可以按与示例 1 相同的路径来砍掉所有的树。
(0,0) 位置的树，可以直接砍去，不用算步数。提示：
m == forest.lengthn == forest[i].length1 <= m, n <= 500 <= forest[i][j] <= 109
算法思路
- 先找出砍树的顺序；
- 然后按照砍树的顺序，一个一个的用
bfs求出最短路即可。
代码实现
class Solution {
int m,n;
public:
int cutOffTree(vector<vector<int>>& forest) {
m = forest.size();
n = forest[0].size();
vector<pair<int, int>> trees;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(forest[i][j] > 1)
trees.push_back({i,j});
sort(trees.begin(), trees.end(), [&](const pair<int, int>& p1, const pair<int, int>& p2){
return forest[p1.first][p1.second] < forest[p2.first][p2.second];
});
int x = 0, y = 0;
int ret = 0;
for(auto& [a,b] : trees)
{
int step = bfs(forest,x,y,a,b);
if(step == -1)
return -1;
ret+=step;
x=a,y=b;
}
return ret;
}
bool vis[51][51];
int dx[4] = {0,0,1,-1};
int dy[4] = {-1,1,0,0};
int bfs(vector<vector<int>>& forest,int bx,int by, int ex, int ey)
{
if(bx == ex & by == ey) return 0;
memset(vis, 0, sizeof(vis));
queue<pair<int, int>> q;
q.push({bx,by});
vis[bx][by] = true;
int step = 0;
while(q.size())
{
step++;
int k = q.size();
while(k--)
{
auto [a,b] = q.front();
q.pop();
for(int i = 0; i < 4; i++)
{
int x = a+dx[i], y = b+dy[i];
if(x>=0 && x<m && y>=0 && y<n && forest[x][y] && vis[x][y]==false)
{
if(x==ex && y==ey)
return step;
q.push({x,y});
vis[x][y] = true;
}
}
}
}
return -1;
}
};
⚠️ 写在最后：以上内容是我在学习以后得一些总结和概括，如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流！！！