【每日算法】专题十六_BFS 解决最短路问题
本文探讨了BFS（广度优先搜索）算法在解决最短路问题中的应用，重点分析了其在无权图或边权为1的图中的高效性。BFS通过分层遍历和队列管理，保证首次访问目标节点时即得到最短路径。文章通过四个LeetCode例题（迷宫最近出口、最小基因变化、单词接龙、高尔夫砍树）详细阐释了BFS的实现细节：1）使用队列控制访问顺序；2）维护visited标记避免重复；3）分层扩展时步数统计；4）针对不同问题的特殊处理
·
1. 算法思想
BFS（广度优先搜索）解决最短路问题的核心思想是通过分层遍历，优先访问距离起点更近的节点，从而在首次到达目标节点时得到最短路径，具体可总结为以下几点：
1. 适用场景
- 针对无权图或边权值均为 1 的图（包括网格、树等结构），此时 “路径长度” 等价于 “边的数量”，BFS 能高效找到从起点到目标节点的最短路径。
2. 核心逻辑：分层扩散与首次访问
- 分层遍历：从起点开始，按照 “与起点的距离” 逐层访问节点 —— 先访问距离为 1 的所有节点，再访问距离为 2 的所有节点，以此类推。
- 首次命中即最短：由于按距离递增顺序遍历，当目标节点首次被访问时，经过的路径必然是最短的（不存在更短路径，否则会更早被访问）。
3. 实现关键：队列与 visited 标记
- 队列（Queue）：作为 BFS 的核心数据结构，用于存储待访问的节点。每次从队头取出节点，将其未访问的邻接节点加入队尾，保证按 “距离递增” 的顺序处理节点。
- visited 标记：记录已访问的节点，避免重复访问（防止循环遍历，同时确保每个节点只被距离最短的路径访问一次）。
4. 路径记录方式
- 若需要输出具体路径，可额外维护一个 “前驱节点” 数组，记录每个节点是从哪个节点访问而来。当到达目标节点后，通过回溯前驱节点即可还原最短路径。
5. 算法步骤示例
- 初始化队列，将起点加入队列，并标记为已访问。
- 若队列不为空，取出队头节点，检查是否为目标节点：是则结束，返回当前距离；否则继续。
- 遍历该节点的所有邻接节点，若未被访问，则标记为已访问，记录其距离（当前节点距离 + 1），并加入队列。
- 重复步骤 2-3，直至找到目标节点或队列为空（无路径）。
综上，BFS 通过 “分层遍历 + 队列管理” 的方式，在无权图中以O(N+M)（N 为节点数，M 为边数）的时间复杂度高效求解最短路问题，核心优势是 “首次访问即最短” 的特性。
2. 例题
2.1 迷宫中离入口最近的出口
1926. 迷宫中离入口最近的出口 - 力扣（LeetCode）
核心思路如下：
1. 问题理解
- 给定一个迷宫（二维字符数组），找到从起点
entrance到任意边界出口的最短路径长度。 - 出口条件：到达边界（第一行 / 列或最后一行 / 列）且非起点。
- 移动规则：每次只能向上下左右四个方向移动一格，且只能走空地（
.）。
2. BFS 算法设计
核心数据结构
- 队列
q：存储待扩展的节点（坐标），保证按层次遍历。 - 访问数组
vis：标记已访问的位置，避免重复访问。
分层扩展策略
- 外层循环：每一轮处理当前队列中的所有节点，代表 “走一步”。
- 内层循环：遍历当前节点的四个方向，若新位置合法（空地且未访问），则加入队列。
- 步数记录：每扩展一层（外层循环），步数
ret加 1。
3. 关键点分析
-
边界判断：
- 扩展新位置时，先检查是否在迷宫范围内且为空地（
maze[x][y] == '.'）。 - 若新位置同时是边界且非起点，立即返回当前步数
ret。
- 扩展新位置时，先检查是否在迷宫范围内且为空地（
-
起点处理：
- 初始化时将起点标记为已访问，避免误判为出口。
-
方向数组优化：
- 使用
dx和dy数组表示四个方向的偏移量，简化代码逻辑。
- 使用
4. 复杂度分析
- 时间复杂度：\(O(nm)\)，其中 n 和 m 分别为迷宫的行数和列数。每个位置最多被访问一次。
- 空间复杂度：\(O(nm)\)，主要用于队列和访问数组。
5. 算法流程
- 初始化：将起点加入队列并标记为已访问。
- 逐层扩展：
- 每轮处理队列中的所有节点（当前层），步数加 1。
- 对每个节点的四个方向进行检查，若新位置合法且未访问：
- 若是边界出口，返回当前步数。
- 否则标记为已访问并加入队列。
- 无解处理：若队列为空仍未找到出口，返回
-1。
总结
该算法通过 BFS 的分层遍历特性，确保首次到达边界出口时路径最短。关键在于合理使用队列和访问标记，以及对边界条件的细致处理。
class Solution {
public:
typedef pair<int, int> PII;
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int n = maze.size(), m = maze[0].size();
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int vis[100][100];
memset(vis, 0, sizeof(vis));
int ret = 0;
queue<PII> q;
q.push({entrance[0], entrance[1]});
vis[entrance[0]][entrance[1]] = true;
while(q.size())
{
++ret;
int sz = q.size();
for(int j = 0; j < sz; ++j) // 走完每步能走的所有格子算一步
{
// 将每次能走的格子带进去，
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 < n && y >= 0 && y < m && maze[x][y] == '.' && !vis[x][y])
{
if(x == 0 || x == n - 1 || y == 0 || y == m - 1) return ret;
vis[x][y] = true;
q.push({x, y});
}
}
}
}
return -1;
}
};2.2 最小基因变化
核心思路如下：
1. 问题理解
- 从起始基因
startGene出发，每次只能变异一个字符，求变为目标基因endGene的最少变异次数。 - 合法变异条件：每次变异后的新基因必须存在于基因库
bank中。
2. BFS 算法设计
核心数据结构
- 队列
q：存储待扩展的基因序列，保证按层次遍历。 - 哈希集合
vis：记录已访问的基因，避免重复处理。 - 哈希集合
hash：快速判断某个基因是否存在于基因库中。
分层扩展策略
- 外层循环：每一轮处理当前队列中的所有基因，代表 “变异一步”。
- 内层循环：对每个基因的每个位置尝试替换为其他三种碱基（A/C/G/T），生成新基因。
- 步数记录：每扩展一层（外层循环），步数
ret加 1。
3. 关键点分析
-
变异生成：
- 对每个基因的每个位置，依次替换为
ACGT中的其他字符，生成新基因。 - 例如，对位置
i的字符，尝试替换为A、C、G、T，检查是否合法。
- 对每个基因的每个位置，依次替换为
-
合法性检查：
- 新基因必须存在于基因库
bank中（通过hash判断）。 - 新基因未被访问过（通过
vis判断）。
- 新基因必须存在于基因库
-
提前终止条件：
- 若当前变异直接得到
endGene，立即返回当前步数ret。
- 若当前变异直接得到
4. 复杂度分析
- 时间复杂度：\(O(N \times L)\)，其中 N 为基因库大小，L 为基因长度（本题中 \(L=8\)）。每个基因最多被扩展一次，每次扩展需尝试 \(L \times 3\) 种变异。
- 空间复杂度：\(O(N)\)，主要用于存储队列和访问集合。
5. 算法流程
-
初始化：
- 将起始基因加入队列，并标记为已访问。
- 检查目标基因是否存在于基因库中，若不存在直接返回
-1。
-
逐层扩展：
- 每轮处理队列中的所有基因（当前层），步数加 1。
- 对每个基因的每个位置生成所有可能的变异：
- 若变异合法且未访问：
- 若是目标基因，返回当前步数。
- 否则标记为已访问并加入队列。
- 若变异合法且未访问：
-
无解处理：若队列为空仍未找到目标基因，返回
-1。
总结
该算法通过 BFS 的分层遍历特性，确保首次到达目标基因时变异次数最少。关键在于合理生成变异并利用哈希集合快速判断合法性，避免无效搜索。
class Solution {
public:
int minMutation(string startGene, string endGene, vector<string>& bank) {
unordered_set<string> vis; // 标记已搜索过的
unordered_set<string> hash(bank.begin(), bank.end());
if(startGene == endGene) return 0;
if(!hash.count(endGene)) return -1;
string change("ACGT");
queue<string> q;
q.push(startGene);
int ret = 0;
while(q.size())
{
++ret;
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] = change[j];
if(hash.count(tmp) && !vis.count(tmp))
{
if(tmp == endGene) return ret;
q.push(tmp);
vis.insert(tmp);
}
}
}
}
}
return -1;
}
};2.3 单词接龙
核心思路如下：
1. 问题理解
- 从起始单词
beginWord出发，每次只能改变一个字母，求变为目标单词endWord的最短转换序列长度。 - 合法转换条件：每次转换后的新单词必须存在于字典
wordList中。
2. BFS 算法设计
核心数据结构
- 队列
q：存储待扩展的单词，保证按层次遍历。 - 哈希集合
vis：记录已访问的单词，避免重复处理。 - 哈希集合
hash：快速判断某个单词是否存在于字典中。
分层扩展策略
- 外层循环：每一轮处理当前队列中的所有单词，代表 “转换一步”。
- 内层循环：对每个单词的每个位置尝试替换为其他 25 个字母，生成新单词。
- 步数记录：每扩展一层（外层循环），步数
ret加 1。初始步数为 1（包含起始单词）。
3. 关键点分析
-
单词生成：
- 对每个单词的每个位置，依次替换为
a到z的其他字母，生成新单词。 - 例如，对位置
i的字母，尝试替换为除原字母外的所有可能字母。
- 对每个单词的每个位置，依次替换为
-
合法性检查：
- 新单词必须存在于字典
wordList中（通过hash判断）。 - 新单词未被访问过（通过
vis判断）。
- 新单词必须存在于字典
-
提前终止条件：
- 若当前转换直接得到
endWord，立即返回当前步数ret。
- 若当前转换直接得到
4. 复杂度分析
- 时间复杂度：\(O(N \times L \times 26)\)，其中 N 为字典大小，L 为单词长度（本题中循环固定为 8 次）。每个单词最多被扩展一次，每次扩展需尝试 \(L \times 25\) 种转换。
- 空间复杂度：\(O(N)\)，主要用于存储队列和访问集合。
5. 算法流程
-
初始化：
- 将起始单词加入队列，并标记为已访问。
- 检查目标单词是否存在于字典中，若不存在直接返回 0。
-
逐层扩展：
- 每轮处理队列中的所有单词（当前层），步数加 1。
- 对每个单词的每个位置生成所有可能的转换：
- 若转换合法且未访问：
- 若是目标单词，返回当前步数。
- 否则标记为已访问并加入队列。
- 若转换合法且未访问：
-
无解处理：若队列为空仍未找到目标单词，返回 0。
总结
该算法通过 BFS 的分层遍历特性，确保首次到达目标单词时转换序列最短。关键在于合理生成转换并利用哈希集合快速判断合法性，避免无效搜索。
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> vis;
unordered_set<string> hash(wordList.begin(), wordList.end());
if(beginWord == endWord) return 0;
if(!hash.count(endWord)) return 0;
queue<string> q;
q.push(beginWord);
int ret = 1;
while(q.size())
{
++ret;
int sz = q.size();
while(sz--)
{
string tmp = q.front();
q.pop();
for(int i = 0; i < 8; ++i)
{
string t = tmp;
for(char ch = 'a'; ch <= 'z'; ++ch)
{
t[i] = ch;
if(hash.count(t) && !vis.count(t))
{
if(t == endWord) return ret;
q.push(t);
vis.insert(t);
}
}
}
}
}
return 0;
}
};2.4 为高尔夫比赛砍树
核心思路及细节如下：
一、核心目标
从固定起点 (0,0) 出发，按树的高度从小到大依次砍伐所有树，计算总最短路径步数。若起点是障碍（0）、无法到达某棵树，返回 -1。
二、核心思路拆解
1. 树的收集与排序（按高度从小到大）
- 数据结构：使用小顶堆（
priority_queue）配合自定义比较器cmp，确保每次取出的是当前未砍伐的树中最矮的一棵。cmp比较器逻辑：通过全局变量fore访问树高，return fore[x1][y1] > fore[x2][y2]实现小顶堆（堆顶为最小树高）。
- 收集条件：仅收集
forest[i][j] > 1的树（隐含逻辑：1可能不视为树，或题目中树高至少为 2），存入堆中自动排序。
2. 路径计算（BFS 求最短路径）
- 核心逻辑：对每棵待砍伐的树，通过 BFS 计算从当前位置到目标树的最短路径步数，累加总步数。
- BFS 细节：
- 起始位置判断：若当前位置就是目标树位置（如起点
(0,0)是最矮树），直接返回0步（if (cur_x == i && cur_y == j) return 0）。 - 队列与访问标记：用队列存储待访问节点，
vis数组标记已访问位置，避免重复遍历和循环路径。 - 移动条件：仅允许移动到非障碍区域（
forest[x][y] != 0），且未访问过的位置。 - 步数计算：每轮 BFS 处理当前层所有节点时，步数
step加 1（代表 “走一步”），找到目标树时立即返回当前步数。
- 起始位置判断：若当前位置就是目标树位置（如起点
3. 整体流程控制
- 起点合法性检查：若
forest[0][0] == 0（起点是障碍），直接返回-1。 - 循环砍伐：从堆中依次取出最矮树，调用 BFS 计算当前位置到目标树的步数，累加总步数
ret，并更新当前位置为目标树位置。 - 障碍处理：若 BFS 返回
-1（无法到达某棵树），整体返回-1。 - 访问标记重置：每处理完一棵树下，用
memset(vis, 0, sizeof(vis))重置访问标记，避免影响下一次 BFS。
三、关键细节说明
- 全局变量
fore的作用：存储森林矩阵，供cmp比较器访问树高（因比较器无法直接访问forest参数，通过全局变量传递）。 - BFS 步数计算逻辑：
step初始为 0，每轮循环（处理一层节点）后step++，确保每一步对应实际移动距离。 - 边界检查：
x >= 0 && x < n && y >= 0 && y < m确保移动不超出森林范围。 - 树高排序的必要性：按从小到大砍伐是题目隐含规则（如 “必须先砍矮树才能砍高树”），小顶堆是高效实现方式。
vector<vector<int>> fore;
class Solution {
typedef pair<int, int> PII;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
bool vis[50][50] = {false};
int n, m;
public:
struct cmp
{
// 按照树的高度进行排序
bool operator()(PII& p1, PII& p2)
{
auto& [x1, y1] = p1;
auto& [x2, y2] = p2;
return fore[x1][y1] > fore[x2][y2];
}
};
int cutOffTree(vector<vector<int>>& forest) {
fore = forest;
n = forest.size(), m = forest[0].size();
if(forest[0][0] == 0) return -1;
// 找到所有树并排序
priority_queue<PII, vector<PII>, cmp> tree;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
if(forest[i][j] > 1)
tree.push({i, j});
}
}
int ret = 0;
int cur_x = 0, cur_y = 0; // 记录起始坐标
while(tree.size())
{
auto [sx, sy] = tree.top();
tree.pop();
int step = bfs(forest, sx, sy, cur_x, cur_y); // 记录起始位置到下一个位置的最短步数
if(step == -1) return -1;
ret += step;
cur_x = sx, cur_y = sy;
memset(vis, 0, sizeof(vis));
}
return ret;
}
int bfs(vector<vector<int>>& forest, int i, int j, int cur_x, int cur_y)
{
// 起始位置就是目标位置，也就是当{0, 0}位置是第一颗要砍的树时
if (cur_x == i && cur_y == j) return 0;
queue<PII> q;
q.push({cur_x, cur_y});
vis[cur_x][cur_y] = true;
int step = 0;
while(q.size())
{
int sz = q.size();
++step; // 走一步
while(sz--)
{
auto [a, b] = q.front();
q.pop();
for(int k = 0; k < 4; ++k)
{
int x = a + dx[k], y = b + dy[k];
if(x >= 0 && x < n && y >= 0 && y < m && forest[x][y] != 0 && !vis[x][y])
{
if(x == i && y == j) return step; // 找到下一个位置了
q.push({x, y});
vis[x][y] = true;
}
}
}
}
return -1; // 到达不了下一个位置
}
};
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
19
0- 0
已为社区贡献1条内容
所有评论(0)