当前位置：首页 > ops >正文

【算法-BFS 解决最短路问题】探索BFS在图论中的应用：最短路径问题的高效解法

ops 2025/7/17 7:45:50

在这里插入图片描述

算法	相关知识点	可以通过点击	以下链接进行学习	一起加油！

在图论中，最短路径问题是一个常见的挑战，广泛应用于路由、网络和交通等领域。对于无权图，广度优先搜索（BFS）提供了一种高效且简洁的解法。本文将简要介绍BFS算法的原理，并探讨其在解决最短路径问题中的应用。

请添加图片描述

Alt

🌈个人主页：是店小二呀
🌈C/C++专栏：C语言\ C++
🌈初/高阶数据结构专栏：初阶数据结构\ 高阶数据结构
🌈Linux专栏： Linux
🌈算法专栏：算法
🌈Mysql专栏:Mysql

🌈你可知:无人扶我青云志我自踏雪至山巅请添加图片描述

文章目录

前言
- 1926. 迷宫中离入口最近的出口
- 433. 最小基因变化
- 127. 单词接龙
- 675. 为高尔夫比赛砍树

前言

本专题主要使用 BFS 来解决最短路径问题，特别是边权为 1 的最短路径问题。

对于此类问题，解决方法是从起点开始，使用 BFS 进行搜索。由于每次扩展都是按层进行的，最短路径的长度即为 BFS 扩展的层数。通过使用队列 [sz, q] 来实现 BFS 扩展，sz 用来记录当前层的节点数，q 则是队列，存储待扩展的节点。每扩展一层，路径长度就增加 1，直到找到目标节点或遍历完所有可达节点。

简而言之，BFS 的层次遍历方式保证了每次访问的节点都按最短路径顺序，因此能够高效地求解边权为 1 的最短路径问题。

在这里插入图片描述

1926. 迷宫中离入口最近的出口

【题目】：1926. 迷宫中离入口最近的出口

在这里插入图片描述

【算法思路】

在这里插入图片描述

这类问题的解决思路与 “BFS 解决 Flood Fill 算法” 的思路非常相似。两者的核心思想都是通过 BFS 遍历图或者矩阵，但在最短路径问题中，我们需要在扩展的过程中记录层数，也就是每次扩展的次数，这样可以得到最短路径。

【代码实现】

class Solution {
public:int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};bool vis[101][101];int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {int 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 level = 1;while(!q.empty()){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 + dx[k], y = b + dy[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 level;q.push({x,y});vis[x][y] = true;}}}level++;}return -1;}
};

433. 最小基因变化

【题目】：433. 最小基因变化

在这里插入图片描述

【算法思路】
在这里插入图片描述

【代码实现】

class Solution {
public:int minMutation(string startGene, string endGene, vector<string>& bank) {unordered_set<string> vis;//标识是否出现过unordered_set<string> hash(bank.begin(), bank.end());//标识库string change = "ACGT";//处理边界情况if(startGene == endGene) return 0;if(!hash.count(endGene)) return -1;//BFSqueue<string> q;q.push(startGene);vis.insert(startGene);int ret = 0;while(q.size()){int sz= q.size();ret++;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;}
};

127. 单词接龙

【题目】：127. 单词接龙

在这里插入图片描述

【算法思路】

在这里插入图片描述

解法同"433. 最小基因变化"是一致的，不过本道题需要求"单词数量"所以ret初始化为1。

【代码实现】

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> vis(wordList.begin(), wordList.end());unordered_set<string> hash;if(beginWord == endWord) return 0;if(!vis.count(endWord)) return 0;queue<string> q;q.push(beginWord);hash.insert(beginWord);int n = beginWord.size();int ret = 1;while(q.size()){int sz = q.size();ret++;while(sz--){string t= q.front();q.pop();for(int i = 0; i < n; i++){string tmp = t;for(char ch = 'a'; ch <= 'z'; ch++){tmp[i] = ch;if(vis.count(tmp) && !hash.count(tmp)){if(tmp == endWord) return ret;q.push(tmp);hash.insert(tmp);}}}}}return 0;}
};

675. 为高尔夫比赛砍树

【题目】：675. 为高尔夫比赛砍树

在这里插入图片描述

【算法思路】

在这里插入图片描述

通过题目分析，可以将问题转化为若干个迷宫问题。我们只需记录每次的起点和终点，并统计步数。同时，为了满足树的高度限制，可以使用数组存储树的坐标（按照顺序排序）。之后，通过不断进行BFS来求解。

通过 for(auto& [a, b] : trees) 可以依次取出需要砍树的坐标和新的起点进行BFS。在BFS过程中，记得更新 vis 数组，避免上一轮的数据影响到当前轮次的结果。

【代码实现】

class Solution {
public:int m, n;int cutOffTree(vector<vector<int>>& forest) {m = forest.size(), n = forest[0].size();//1.获得砍树的顺序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});//2.获得砍树顺序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];});//3.开始砍树int bx = 0, by = 0;int ret = 0;for(auto& [a, b] : trees){int step = bfs(forest,bx, by, a, b);if(step == -1) return -1;ret += step;bx = a, by = b; }return ret;}int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};bool vis[51][51];int bfs(vector<vector<int>>& forest, int bx, int by, int ex, int ey){if(bx == ex && by == ey) return 0;queue<pair<int,int>> q;q.push({bx, by});memset(vis, 0, sizeof vis);vis[bx][by] = true;int step = 0;while(q.size()){step++;int sz =q.size();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 < m && y >= 0 && y < n && !vis[x][y] && forest[x][y] != 0){if(x == ex && y == ey) return step;q.push({x, y});vis[x][y] = true;}}}}return -1;}
};