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

算法魅力-BFS解决最短路问题

java 2025/7/13 9:48:18

前言

BFS俗称广度优先搜索，用“队列”一圈一圈向外扩展。

最短路径问题是图论中的经典问题，指的是：

从起点出发，经过若干条边，到达终点所花费的路径长度最小。

BFS解决最短路

📌 BFS 与最短路径的关系（关键点）

✅ 结论

在无权图中，BFS 是求解最短路径问题的最优算法。

✅ 解释

无权图：图中每条边的权重（代价）都是相等的（比如都为 1）；
BFS（广度优先搜索）天然按“层级”来搜索节点：
- 第一次访问某个点，一定是走的最短路径到达的；
- 所以，第一次访问即记录其最短距离。

题目实操

迷宫中离入口最近的出口

1926. 迷宫中离入口最近的出口 - 力扣（LeetCode）

给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。

每一步操作，你可以往上，下，左或者右移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近的出口。出口的含义是 maze 边界上的 空格子。entrance 格子不算出口。

请你返回从 entrance 到最近出口的最短路径的步数，如果不存在这样的路径，请你返回 -1 。

可以从起点开始层序遍历，并且在遍历的过程中记录当前遍历的层数。这样就能在找到出口的

时候，得到起点到出口的最短距离。出口的临近值是第一行，第一列或者最后一行，最后一列。

从起点向四周走一步都可以看成权值为1，然后相邻格子为点。

class Solution {int dx[4]={-1,0,0,1};int dy[4]={0,1,-1,0};bool vis[101][101]={false};
public:int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {int m=maze.size();int 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.empty()){step++;int num=q.size();for(int i=0;i<num;i++){auto [a,b]=q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k];int 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 step;//step++;q.push({x,y});vis[x][y]=true;}}}}return -1;}
};

最小基因变化

433. 最小基因变化 - 力扣（LeetCode）

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

将每次字符串的变化抽象为两个顶点和一条边话，就变成了边权为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());string gene="AGCT";if(startGene==endGene) return 0;if(!hash.count(endGene)) return -1;queue<string> q;q.push(startGene);vis.insert(startGene);int step=0;while(!q.empty()){step++;int sz=q.size();while(sz--){string s=q.front();q.pop();for(int i=0;i<8;i++){string tmp=s;for(int j=0;j<4;j++){tmp[i]=gene[j];if(hash.count(tmp)){if(tmp==endGene) return step;if(!vis.count(tmp)){vis.insert(tmp);q.push(tmp);}}}}}}return -1;}};

单词接龙

127. 单词接龙 - 力扣（LeetCode）

在字典（单词列表） wordList 中，从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

序列中第一个单词是 beginWord 。
序列中最后一个单词是 endWord 。
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典 wordList 中的单词。

给定两个长度相同但内容不同的单词 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" 不在字典中，所以无法进行转换。

本题思路与上面题目几乎一模一样，就是字符串长度和替换的字母变了。

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(hash.count(endWord)==0) return 0;queue<string>q;q.push(beginWord);vis.insert(beginWord);int step=1;while(!q.empty()){step++;int sz=q.size();while(sz--){string s=q.front();q.pop();for(int i=0;i<beginWord.length();i++){string tmp=s;for(char ch='a';ch <='z';ch++){tmp[i]=ch;if(hash.count(tmp) && !vis.count(tmp)){if(tmp==endWord) return step;q.push(tmp);vis.insert(tmp);}}}}}return 0;}
};

为高尔夫比赛砍树

675. 为高尔夫比赛砍树 - 力扣（LeetCode）

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示，在这个矩阵中：

0 表示障碍，无法触碰
1 表示地面，可以行走
比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度

每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。

你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。

你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。如果你无法砍完所有的树，返回 -1 。

可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

class Solution {int n,m;
public:int cutOffTree(vector<vector<int>>& forest) {n=forest.size(),m=forest[0].size();vector<pair<int,int>> v;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(forest[i][j]>1)v.push_back({i,j});}}//对树排序sort(v.begin(),v.end(),[&](pair<int,int> &p1,pair<int,int>&p2){return forest[p1.first][p1.second] < forest[p2.first][p2.second];});int bx=0,by=0;int ret=0;for(int i=0;i<v.size();i++){auto [a,b]=v[i];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,0,0,1};int dy[4]={0,1,-1,0};int bfs(vector<vector<int>>& forest,int ax,int ay,int bx,int by){if(ax==bx && ay==by) return 0;bool vis[51][51]={false};queue<pair<int,int>> q;q.push({ax,ay});vis[ax][ay]=true;int step=0;while(!q.empty()){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];int y=b+dy[k];if(x>=0 && x<n && y>=0 && y<m && !vis[x][y] && forest[x][y]){if(x==bx && y==by) return step;q.push({x,y});vis[x][y]=true;}}}}return -1;}
};

📌 常见应用场景

场景	BFS 应用
🌟 迷宫/网格地图求最短路径	✅
🌐 图中最短边数路径	✅
⏱️ 同步更新层级、状态扩展	✅
🔄 状态变换问题（如传染扩散）	✅