算法思想之 BFS 解决 最短路问题

发布于:2025-08-02 ⋅ 阅读:(15) ⋅ 点赞:(0)

欢迎拜访雾里看山-CSDN博客
本篇主题算法思想之 BFS 解决 最短路问题
发布时间:2025.7.30
隶属专栏算法

在这里插入图片描述

算法介绍

BFS(广度优先搜索)通过 “逐层扩散” 的方式遍历图中节点,这种特性使其在无权图边权相等的图中,能天然找到从起点到目标节点的最短路径。其核心逻辑在于:越早被访问到的节点,距离起点越近。当首次抵达目标节点时,所经过的路径必然是边数最少的最短路径。

算法适用场景

  • 无权图的最短路径计算(如社交网络中两人的最短好友链)
  • 边权值均为 1 的图(如网格中移动一步的代价固定)
  • 迷宫类问题(从起点到终点的最少步数)
  • 层次化结构的遍历(如二叉树的最小深度)

实现步骤与关键要素

  1. 图的表示方式
    • 邻接表:适用于稀疏图,用vector<vector<int>>存储每个节点的邻接节点
    • 邻接矩阵:适用于稠密图,用二维数组graph[i][j]表示节点 i 与 j 是否相连
    • 网格结构:用二维数组表示,通过方向数组遍历相邻单元格
  2. 核心数据结构
    • 队列(queue):存储待访问的节点,保证按层次顺序处理
    • 距离记录(dist):数组或矩阵,记录起点到各节点的最短距离,初始化为 - 1(未访问)
    • 前驱节点(prev):可选,用于回溯还原完整路径
  3. 算法执行流程
    • 初始化:起点入队,距离设为 0
    • 循环处理:
      • 取出队首节点 u,遍历其所有邻接节点 v
      • v 未访问(dist [v] = -1),则设置 dist [v] = dist [u] + 1,记录前驱 prev [v] = u,将 v 入队
      • v 是目标节点,可提前退出循环
    • 结果:dist [目标节点] 即为最短距离,通过 prev 数组可还原路径

例题

迷宫中离入口最近的出口

题目链接

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

题目描述

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

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

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

示例 1

在这里插入图片描述
输入:maze = [[“+”,“+”,“.”,“+”],[“.”,“.”,“.”,“+”],[“+”,“+”,“+”,“.”]], entrance = [1,2]
输出:1
解释:总共有 3 个出口,分别位于 (1,0),(0,2) 和 (2,3) 。
一开始,你在入口格子 (1,2) 处。
你可以往左移动 2 步到达 (1,0) 。
你可以往上移动 1 步到达 (0,2) 。
从入口处没法到达 (2,3) 。
所以,最近的出口是 (0,2) ,距离为 1 步。

示例 2

在这里插入图片描述
输入:maze = [[“+”,“+”,“+”],[“.”,“.”,“.”],[“+”,“+”,“+”]], entrance = [1,0]
输出:2
解释:迷宫中只有 1 个出口,在 (1,2) 处。
(1,0) 不算出口,因为它是入口格子。
初始时,你在入口与格子 (1,0) 处。
你可以往右移动 2 步到达 (1,2) 处。
所以,最近的出口为 (1,2) ,距离为 2 步。

示例 3

在这里插入图片描述
输入:maze = [[“.”,“+”]], entrance = [0,0]
输出:-1
解释:这个迷宫中没有出口。

提示

  • maze.length == m
  • maze[i].length == n
  • 1 <= m, n <= 100
  • maze[i][j] 要么是 '.' ,要么是 '+' 。
  • entrance.length == 2
  • 0 <= entrancerow < m
  • 0 <= entrancecol < n
  • entrance 一定是空格子。

算法思路

利用层序遍历来解决迷宫问题,是最经典的做法。

我们可以从起点开始层序遍历,并且在遍历的过程中记录当前遍历的层数。这样就能在找到出口的时候,得到起点到出口的最短距离

代码实现

class Solution {
    typedef pair<int, int> PII;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {-1, 1, 0, 0};
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size();
        int n = maze[0].size();
        bool vis[101][101];
        memset(vis,0, sizeof(vis));
        queue<PII> q;
        q.push({entrance[0], entrance[1]});
        vis[entrance[0]][entrance[1]] = true;
        int ret = 0;
        while(q.size())
        {
            ret++;
            int k = q.size();
            while(k--)
            {
                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<m && y>=0 && y<n && maze[x][y] == '.' &&vis[x][y] == false)
                    {
                        if(x == 0 || y == 0 || x == m-1 || y == n-1)
                            return ret;
                        vis[x][y] = true;
                        q.push({x,y});
                    }
                }
            }
        }
        return -1;
    }
};

在这里插入图片描述

最小基因变化

题目链接

433. 最小基因变化

题目描述

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

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

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


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

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

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

示例 1

输入:start = “AACCGGTT”, end = “AACCGGTA”, bank = [“AACCGGTA”]
输出:1

示例 2

输入:start = “AACCGGTT”, end = “AAACGGTA”, bank = [“AACCGGTA”,“AACCGCTA”,“AAACGGTA”]
输出:2

示例 3

输入:start = “AAAAACCC”, end = “AACCCCCC”, bank = [“AAAACCCC”,“AAACCCCC”,“AACCCCCC”]
输出:3

提示

  • start.length == 8
  • end.length == 8
  • 0 <= bank.length <= 10
  • bank[i].length == 8
  • startendbank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成

算法思路

如果将每次字符串的变换抽象成图中的两个顶点和一条边的话,问题就变成了 边权为 1的最短路问题

因此,从起始的字符串开始,来一次 bfs 即可。

代码实现

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> hash(bank.begin(), bank.end());
        unordered_set<string> vis;
        
        if(startGene == endGene)
            return 0;
        if(!hash.count(endGene))
            return -1;

        string change = "ACTG";

        queue<string> q;
        q.push(startGene);
        vis.insert(startGene);
        int ret = 0;
        while(q.size())
        {
            ret++;
            int k = q.size();
            while(k--)
            {
                string tmp = q.front();
                q.pop();
                for(int i = 0; i < 8; i++)
                {
                    string t = tmp;
                    for(int j = 0; j < 4; j++)
                    {
                        t[i] = change[j];
                        if(hash.count(t) && !vis.count(t))
                        {
                            if(t == endGene)
                                return ret; 
                            q.push(t);
                            vis.insert(t);
                        }
                    }

                }
            }
        }
        return -1;
    }
};

在这里插入图片描述

单词接龙

题目链接

127. 单词接龙

题目描述

字典 wordList 中从单词 beginWordendWord转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk

  • 每一对相邻的单词只差一个字母。
  • 对于 1 <= i <= k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。
  • sk == endWord


给你两个单词 beginWordendWord 和一个字典 wordList ,返回 从 beginWordendWord最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 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” 不在字典中,所以无法进行转换。

提示

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWordendWordwordList[i] 由小写英文字母组成
  • beginWord != endWord
  • wordList 中的所有字符串 互不相同

算法思路

此题的算法思路和上一题一样!

代码实现

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> hash(wordList.begin(), wordList.end());
        unordered_set<string> vis;
        if(!hash.count(endWord)) return 0;

        int n = endWord.size();
        string change = "abcdefghijklmnopqrstuvwxyz";
        queue<string> q;
        q.push(beginWord);
        if(hash.count(beginWord))
            vis.insert(beginWord);
        int ret = 1;
        while(q.size())
        {
            ret++;
            int k = q.size();
            while(k--)
            {
                string tmp = q.front();
                q.pop();
                for(int i = 0; i < n; i++)
                {
                    string t = tmp;
                    
                    for(int j = 0; j < 26; j++)
                    {
                        t[i] = change[j];
                        if(hash.count(t) && !vis.count(t))
                        {
                            if(t == endWord)
                                return ret;
                            q.push(t);
                            vis.insert(t);
                        }
                    }
                    
                }
            }
        }
        return 0;
    }
};

在这里插入图片描述

为高尔夫比赛砍树

题目链接

675. 为高尔夫比赛砍树

题目描述

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

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


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

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

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

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

示例 1

在这里插入图片描述
输入:forest = [[1,2,3],[0,0,4],[7,6,5]]
输出:6
解释:沿着上面的路径,你可以用 6 步,按从最矮到最高的顺序砍掉这些树。

示例 2

在这里插入图片描述
输入:forest = [[1,2,3],[0,0,0],[7,6,5]]
输出:-1
解释:由于中间一行被障碍阻塞,无法访问最下面一行中的树。

示例 3

输入:forest = [[2,3,4],[0,0,5],[8,7,6]]
输出:6
解释:可以按与示例 1 相同的路径来砍掉所有的树。
(0,0) 位置的树,可以直接砍去,不用算步数。

提示

  • m == forest.length
  • n == forest[i].length
  • 1 <= m, n <= 50
  • 0 <= forest[i][j] <= 109

算法思路

  1. 先找出砍树的顺序;
  2. 然后按照砍树的顺序,一个一个的用 bfs 求出最短路即可。

代码实现

class Solution {
    int m,n;
public:
    int cutOffTree(vector<vector<int>>& forest) {
        m = forest.size();
        n = forest[0].size();
        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});

        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];   
        });

        int x = 0, y = 0;
        int ret = 0;
        for(auto& [a,b] : trees)
        {
            int step = bfs(forest,x,y,a,b);
            if(step == -1)
                return -1;
            ret+=step;
            x=a,y=b;
        }
        return ret;
    }

    bool vis[51][51];
    int dx[4] = {0,0,1,-1};
    int dy[4] = {-1,1,0,0};

    int bfs(vector<vector<int>>& forest,int bx,int by, int ex, int ey)
    {
        if(bx == ex & by == ey) return 0;
        memset(vis, 0, sizeof(vis));
        queue<pair<int, int>> q;
        q.push({bx,by});
        vis[bx][by] = true;
        int step = 0;
        while(q.size())
        {
            step++;
            int k = q.size();
            while(k--)
            {
                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<m && y>=0 && y<n && forest[x][y] && vis[x][y]==false)
                    {
                        if(x==ex && y==ey)
                            return step;
                        q.push({x,y});
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
        
    }
};

在这里插入图片描述

⚠️ 写在最后:以上内容是我在学习以后得一些总结和概括,如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流!!!