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

前言

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

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

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

BFS解决最短路

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

✅ 结论

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

✅ 解释

• 无权图：图中每条边的权重（代价）都是相等的（比如都为 1）；

• BFS（广度优先搜索）天然按“层级”来搜索节点：

  • 第一次访问某个点，一定是走的最短路径到达的；

  • 所以，第一次访问即记录其最短距离。

题目实操 

迷宫中离入口最近的出口

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

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

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

请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -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 适用于 无权图；

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

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

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

✍️ 一句话总结

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