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

前言

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>& maze, vector& entrance) { int m=maze.size(); int n=maze[0].size(); queue<pair> 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=0 && x=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& bank) { unordered_set vis; unordered_set hash(bank.begin(),bank.end()); string gene=\"AGCT\"; if(startGene==endGene) return 0; if(!hash.count(endGene)) return -1; queue 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& wordList) { unordered_set vis; unordered_set hash(wordList.begin(),wordList.end()); if(hash.count(endWord)==0) return 0; queueq; 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>& forest) { n=forest.size(),m=forest[0].size(); vector<pair> v; for(int i=0;i<n;i++){ for(int j=0;j1) v.push_back({i,j}); } } //对树排序 sort(v.begin(),v.end(),[&](pair &p1,pair&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>& forest,int ax,int ay,int bx,int by){ if(ax==bx && ay==by) return 0; bool vis[51][51]={false}; queue<pair> 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=0 && x=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 适用于 无权图；

• 有边权的图（如权重为正/负/不同）：需要 Dijkstra / SPFA / Bellman-Ford；

• 使用 queue，不要改用 stack（那是 DFS）；

• 必须使用 vis 数组或 dist[] 来避免重复访问。

✍️ 一句话总结

BFS 是在 无权图中寻找最短路径的“天然之选”，它以层级方式逐步扩展，第一次访问一个点就是最短路径。