BFS算法解决最短路径问题（典型算法思想）—— OJ例题算法解析思路

目录

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

算法代码： 

代码分析

各个部分的解释

注意事项

整体的含义

具体情况

使用 e[0] 和 e[1] 的优势

总结

示例代码中的用法

整体流程

示例

复杂度分析

总结

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

算法代码： 

代码逻辑思路

数据结构准备

边界条件检查

广度优先搜索（BFS）初始化

BFS 主循环

返回结果

总结

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

算法代码： 

代码逻辑思路

数据结构准备

边界条件检查

BFS 初始化

BFS 主循环

返回结果

关键点总结

广度优先搜索（BFS）

字母替换的生成

访问标记

复杂度分析

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

算法代码： 

代码逻辑思路

数据结构和变量初始化

步骤一：收集树的位置并排序

步骤二：依次砍树

BFS 函数

关键点总结

数据结构和算法

边界条件的处理

复杂度分析

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

算法代码： 

class Solution {
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& e) {
        int m = maze.size(), n = maze[0].size();
        bool vis[m][n];
        memset(vis, 0, sizeof vis);
        queue<pair<int, int>> q;
        q.push({e[0], e[1]});
        vis[e[0]][e[1]] = true;
        int step = 0;
        while (q.size()) {
            step++;
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                auto [a, b] = q.front();
                q.pop();
                for (int j = 0; j < 4; j++) {
                    int x = a + dx[j], y = b + dy[j];
                    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;
                        q.push({x, y});
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
};

代码分析

1. 类声明和成员变量：

   class Solution {
       int dx[4] = {0, 0, 1, -1};
       int dy[4] = {1, -1, 0, 0};
   

   • dx 和 dy 数组用于表示四个方向的移动。dx 和 dy 分别表示水平方向和垂直方向的增量，方向分别是右、左、下、上。

2. 公共成员函数：

   public:
       int nearestExit(vector<vector<char>>& maze, vector<int>& e) {
           int m = maze.size(), n = maze[0].size();
           bool vis[m][n];
           memset(vis, 0, sizeof vis);
           queue<pair<int, int>> q;
           q.push({e[0], e[1]});
           vis[e[0]][e[1]] = true;
           int step = 0;
   

   • m 和 n 分别是迷宫的行数和列数。

   • vis 是一个二维数组，用来记录每个位置是否已访问过，防止重复访问。

   • q 是一个队列，用于广度优先搜索。队列存储的是坐标对 (a, b)，表示当前位置。

   • 初始时，将入口位置 e[0], e[1] 入队，并将其标记为已访问。

   • memset(vis, 0, sizeof vis); 是 C 和 C++ 中的一个函数调用，主要用于初始化数组或内存区域。具体来说，这个语句的含义如下：

     各个部分的解释

   • memset 函数：

     • memset 是一个标准库函数，定义在 <cstring> 头文件中。它的作用是将指定内存区域的内容设置为某个值。

     • 函数原型如下：

       void* memset(void* ptr, int value, size_t num);
       

     • 其中 ptr 是要设置的内存区域的起始地址，value 是要设置的值，num 是要设置的字节数。

   • vis：

     • 在这段代码中，vis 是一个二维布尔数组，用于记录在迷宫中每个位置是否已被访问过。在此上下文中，vis 数组通常是用来避免重复访问同一位置。

   • 0：

     • 这里的 0 表示将 vis 数组的所有元素设置为 0。在布尔数组中，0 通常被视为 false，这意味着在初始化时，所有位置都被标记为未访问。

   • sizeof vis：

     • sizeof vis 获取 vis 数组所占的字节数。这样，memset 会将整个数组的内存区域都设置为 0。

   • 假设 vis 是一个 2D 数组，大小为 5 x 5，初始状态可能是未定义的。通过 memset 初始化后，vis 将变成：

     vis = {
         {false, false, false, false, false},
         {false, false, false, false, false},
         {false, false, false, false, false},
         {false, false, false, false, false},
         {false, false, false, false, false}
     };
     

     注意事项

   • memset 只适用于简单类型的数组，如 int、char 和 bool 等，因为它是按字节设置的。对于包含复杂类型（如类对象或结构体）的数组，通常应使用构造函数或相应的初始化方法。

   • 对于 bool 类型的数组，使用 memset 进行初始化是可以的，因为 0 会被解释为 false。但是，在处理其他类型（如 int、float 等）时，要确保理解 0 的含义。

   • 整体的含义

     因此，memset(vis, 0, sizeof vis); 的作用是将整个 vis 数组的所有元素初始化为 false（或 0），以表明在开始搜索之前，所有位置都未被访问过。这对于 BFS 或 DFS 等算法是非常重要的，因为我们需要跟踪哪些位置已经被访问，以避免无限循环和多次访问同一位置。

   • 在给定的代码中，入口位置使用 e[0] 和 e[1] 表示的原因是因为 e 是一个向量（或数组），通常用于存储二维空间中的坐标。具体来说，e 表示入口点的坐标，通常形式如下：

   • e[0] 表示行索引（即纵坐标）。

   • e[1] 表示列索引（即横坐标）。

   • 具体情况

     在这段代码中，e 是一个 vector<int> 类型的变量，用来存储迷宫中入口的坐标。例如，如果入口位置为 (2, 3)，则可以表示为 e 的内容如下：

     vector<int> e = {2, 3}; // e[0] = 2 (行), e[1] = 3 (列)
     

     使用 e[0] 和 e[1] 的优势

   • 清晰的语义：

     • 使用 e[0] 和 e[1] 来表示入口位置的行和列，可以让代码更加清晰易懂。读者可以很容易地理解 e[0] 是行坐标，e[1] 是列坐标。

   • 简洁性：

     • 将入口位置封装在一个数组或向量中，使得在参数传递和处理时可以更简洁。例如，函数可以直接接受 vector<int>& e 而不是两个单独的整数参数，这样可以减少函数参数的数量，并保持相关数据的整合。

   • 灵活性：

     • 如果需要扩展功能，比如处理多入口或不同的坐标系统，可以很方便地调整 e 的结构，而不需要更改函数签名或大量代码。

   • 这里使用 e[0] 和 e[1] 将入口的坐标放入队列中以进行后续的搜索。

     总结

     使用 e[0] 和 e[1] 表示入口位置的行和列索引是一个常见且有效的做法。这种方式将坐标封装在数组中，不仅提高了代码的可读性和可维护性，也为后续的扩展和修改提供了便利。

     示例代码中的用法

     在给定的代码中，入口位置 e 被用于初始化 BFS 的起始点，例如：

     q.push({e[0], e[1]});
     

3. 广度优先搜索（BFS）：

   while (q.size()) {
       step++; // 每经过一层，步数加1
       int sz = q.size(); // 当前队列的大小，即当前层的节点数
       for (int i = 0; i < sz; i++) {
           auto [a, b] = q.front(); // 获取队头元素
           q.pop();
           for (int j = 0; j < 4; j++) { // 遍历四个方向
               int x = a + dx[j], y = b + dy[j];
               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;
                   q.push({x, y}); // 将该位置加入队列
                   vis[x][y] = true; // 标记该位置为已访问
               }
           }
       }
   }
   return -1; // 如果队列为空，说明没有出口，返回-1
   

   • 外层 while 循环通过队列进行层级遍历（即 BFS）。

   • 每次处理一层节点，step 记录当前的步数。

   • 内层循环对当前节点的四个方向进行探索，检查新位置是否符合条件：

     • 是否在迷宫的边界上。

     • 是否是可走的位置（maze[x][y] == '.'）。

     • 是否未被访问过（!vis[x][y]）。

   • 如果找到迷宫边界上的出口，则返回当前步数 step。

   • 如果没有找到出口，则将当前合法位置入队，并标记为已访问。

4. 函数返回：

   • 如果遍历完所有可能的路径都没有找到出口，返回 -1，表示无法到达出口。

整体流程

• 从入口点开始，广度优先搜索每一层的所有可达点。

• 在搜索过程中，如果到达迷宫的边界（表示是一个出口），返回当前步数。

• 如果搜索完所有点都没有找到出口，返回 -1。

示例

假设输入的迷宫是：

maze = {
  {'+', '+', '+', '+', '+', '+'},
  {'+', '.', '.', '.', '.', '+'},
  {'+', '.', '#', '#', '#', '+'},
  {'+', '.', '#', '.', '#', '+'},
  {'+', '.', '.', '.', 'E', '+'},
  {'+', '+', '+', '+', '+', '+'}
};
e = {1, 1};  // 入口位置

• 初始时，入口位置是 (1, 1)。

• 广度优先搜索会检查四个方向，并在找到 E（出口）时返回当前步数。

复杂度分析

• 时间复杂度：O(m * n)，其中 m 和 n 是迷宫的行数和列数。最坏情况下，我们需要遍历每个点一次。

• 空间复杂度：O(m * n)，用于存储访问标记数组 vis 和队列 q。

总结

这段代码使用广度优先搜索（BFS）算法解决了从入口到达最近出口的问题，适用于迷宫类的最短路径问题。通过逐层扩展搜索范围，确保找到了最短路径。

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

算法代码： 

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; // 如果起始和目标基因相同，返回 0
        if (!hash.count(endGene))
            return -1; // 如果目标基因不在基因库，返回 -1
        
        // BFS 初始化
        queue<string> q;
        q.push(startGene);
        vis.insert(startGene);
        int ret = 0; // 当前变异步数
        
        while (q.size()) {
            ret++; // 每次进入新的层，步数加一
            int sz = q.size(); // 当前层的大小
            
            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]; // 进行替换
                        
                        // 检查新的基因是否在 bank 中且未被访问过
                        if (hash.count(tmp) && !vis.count(tmp)) {
                            if (tmp == endGene)
                                return ret; // 如果找到了目标基因，返回步数
                            q.push(tmp); // 否则入队
                            vis.insert(tmp); // 标记已访问
                        }
                    }
                }
            }
        }
        
        return -1; // 如果遍历完没有找到目标基因，返回 -1
    }
};

代码逻辑思路

1. 数据结构准备

   • 使用 unordered_set<string> vis 来记录已经访问过的基因序列，以避免重复搜索。

   • 使用 unordered_set<string> hash 来存储基因库中的所有基因序列，以便快速查找。

   • 定义一个字符串 change，表示可以变异的基因字符（即 "A", "C", "G", "T"）。

2. 边界条件检查

   • 如果 startGene 等于 endGene，说明已经在目标基因上，返回 0。

   • 如果 endGene 不在 hash 中，说明无法到达目标，返回 -1。

3. 广度优先搜索（BFS）初始化

   • 使用一个队列 queue<string> q，将 startGene 入队，表示从此基因开始进行变异。

   • 将 startGene 标记为已访问。

4. BFS 主循环

   • 使用一个 while 循环，直到队列为空。

   • 在每一层中，记录当前队列的大小 sz，表示当前变异的步数。

   • 对于队列中的每个基因序列：

     • 生成它的所有可能变异序列。

     • 通过外层循环遍历序列的每一个位置（总共 8 个基因）。

     • 对于每个基因位置，使用内层循环遍历变异字符（"A", "C", "G", "T"）。

     • 生成新的基因序列 tmp，如果 tmp 在基因库中且未被访问：

       • 如果 tmp 等于 endGene，返回当前的变异步数 ret。

       • 否则，将 tmp 入队，并标记为已访问。

5. 返回结果

   • 如果 BFS 结束时仍未找到 endGene，返回 -1，表示无法达到目标基因。

总结

• 广度优先搜索（BFS）：使用 BFS 可以确保找到最短路径，因为它逐层扩展搜索的范围，保证了找到目标基因的最小变异步数。

• 边界条件：在处理字符串变异问题时，确保对边界情况进行适当处理。

• 数据结构选择：使用 unordered_set 进行 O(1) 的查找和访问标记，确保算法的效率。

这种方法有效且简洁，可以用于解决类似的最短路径或状态转移问题。

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

算法代码： 

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; // 不在返回0
        queue<string> q; // 初始化队列
        q.push(beginWord); // 将起始单词入队
        vis.insert(beginWord); // 标记起始单词为已访问
        int ret = 1; // 变换步数初始化为1

        while (q.size()) { // BFS循环
            ret++; // 每次进入新的层，步数加1
            int sz = q.size(); // 当前层的大小
            
            while (sz--) { // 遍历当前层的所有单词
                string t = q.front(); // 取出队头单词
                q.pop();
                
                // 对当前单词进行字母替换
                for (int i = 0; i < t.size(); i++) {
                    string tmp = t; // 复制当前单词
                    for (char ch = 'a'; ch <= 'z'; ch++) { // 替换当前字母
                        tmp[i] = ch;
                        // 检查新的单词是否在单词列表中且未被访问过
                        if (hash.count(tmp) && !vis.count(tmp)) {
                            if (tmp == endWord) // 如果找到了目标单词，返回步数
                                return ret;
                            q.push(tmp); // 否则入队
                            vis.insert(tmp); // 标记为已访问
                        }
                    }
                }
            }
        }
        
        return 0; // 如果遍历完没有找到目标单词，返回0
    }
};

代码逻辑思路

1. 数据结构准备

   • 使用 unordered_set<string> hash 来快速存储和查找单词列表中的单词。

   • 使用 unordered_set<string> vis 来标记已经访问过的单词，防止重复搜索。

   • 使用一个队列 queue<string> q 来实现广度优先搜索（BFS），用于按层遍历单词。

2. 边界条件检查

   • 如果 endWord 不在单词列表 hash 中，返回 0，表示无法到达目标单词。

3. BFS 初始化

   • 将 beginWord 入队，并标记为已访问。

   • 初始化步数 ret 为 1，表示当前的变换步骤。

4. BFS 主循环

   • 使用一个 while 循环，当队列不为空时进行搜索。

   • 在每一层中，增加步数 ret，记录当前层的大小 sz。

   • 遍历当前层的单词，根据每个单词生成可能的变换单词：

     • 对于每个字母的位置，尝试用 ‘a’ 到 ‘z’ 的每个字符进行替换，生成新的单词 tmp。

     • 如果 tmp 在 hash 中且未被访问：

       • 如果 tmp 等于 endWord，返回当前的变换步数 ret。

       • 否则，将 tmp 入队，并标记为已访问。

5. 返回结果

   • 如果 BFS 遍历结束仍未找到 endWord，返回 0，表示无法达到目标单词。

关键点总结

1. 广度优先搜索（BFS）

   • BFS 是解决最短路径问题的经典方法，确保找到最少的变换步数。

2. 字母替换的生成

   • 通过遍历每个字母位置，并尝试替换为 ‘a’ 到 ‘z’ 的每个字符来生成新的单词。

3. 访问标记

   • 使用 unordered_set<string> vis 来避免重复处理同一个单词，从而提高效率。

4. 复杂度分析

   • 时间复杂度为 O(N * M * 26)，其中 N 是单词列表的大小，M 是单词的长度。每个单词最多有 M 个位置可以更换，且每个位置有 26 种可能的字符。

   • 空间复杂度为 O(N)，用于存储单词集合和访问标记。

这种方法有效且高效，可以解决类似的单词接龙问题。

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

算法代码： 

class Solution {
    int m, n;

public:
    int cutOffTree(vector<vector<int>>& f) {
        m = f.size(), n = f[0].size();
        // 1. 准备工作：找出砍树的顺序
        vector<pair<int, int>> trees;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (f[i][j] > 1)
                    trees.push_back({i, j});

        // 根据树的高度排序
        sort(trees.begin(), trees.end(),
             [&](const pair<int, int>& p1, const pair<int, int>& p2) {
                 return f[p1.first][p1.second] < f[p2.first][p2.second];
             });
        // 2. 按照顺序砍树
        int bx = 0, by = 0; // 从起点开始
        int ret = 0; // 总步数
        for (auto& [a, b] : trees) {
            int step = bfs(f, bx, by, a, b);
            if (step == -1)
                return -1; // 如果无法到达
            ret += step; // 累加到总步数
            bx = a, by = 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>>& f, int bx, int by, int ex, int ey) {
        if (bx == ex && by == ey)
            return 0; // 如果已经到达目标，不需要步数
        queue<pair<int, int>> q;
        memset(vis, 0, sizeof vis); // 清空访问标记
        q.push({bx, by});
        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 i = 0; i < 4; i++) { // 遍历四个方向
                    int x = a + dx[i], y = b + dy[i];
                    // 检查新的坐标是否合法
                    if (x >= 0 && x < m && y >= 0 && y < n && f[x][y] &&
                        !vis[x][y]) {
                        if (x == ex && y == ey)
                            return step; // 找到了目标树，返回步数
                        q.push({x, y}); // 入队
                        vis[x][y] = true; // 标记为已访问
                    }
                }
            }
        }
        return -1; // 如果没有找到目标树，返回 -1
    }
};

• 代码逻辑思路​​​​​​​

  

  1. 数据结构和变量初始化

     • m 和 n 分别表示网格的行数和列数。

     • trees 用于存储所有树的位置（坐标），并在后续进行排序。

     • bx 和 by 是当前的位置（开始时，通常设定为 (0, 0)），ret 用于累积总步数。

  2. 步骤一：收集树的位置并排序

     • 遍历整个网格 f，找到所有树的位置（即 f[i][j] > 1），并将它们以 (i, j) 的形式存储在 trees 中。

     • 使用 std::sort 对 trees 进行排序，按照树的高度进行升序排列。排序的比较函数使用了 Lambda 表达式。

  3. 步骤二：依次砍树

     • 遍历排序后的 trees，对于每棵树，调用 bfs 函数计算从当前的位置到目标树的步数。

     • 如果 bfs 返回 -1，说明无法到达这棵树，直接返回 -1。

     • 如果可以到达，则将步数累加到 ret，并更新当前位置为当前树的位置。

  4. BFS 函数

     • 该函数负责计算从当前坐标到目标树坐标的最短路径。

     • 如果当前坐标与目标树坐标相同，直接返回 0 步。

     • 使用队列 q 进行广度优先搜索，使用数组 vis 记录已访问的位置。

     • 在每一步中，遍历四个可能的方向（上、下、左、右），如果当前坐标是有效的且未被访问且不是障碍，入队并标记为已访问。

     • 如果在某一步找到了目标树坐标，返回当前步数。

     • 如果队列为空且尚未找到目标，返回 -1。

  关键点总结

  1. 数据结构和算法

     • 使用 std::vector 存储树的位置并进行排序。

     • BFS 用于寻找从一个点到另一个点的最短路径，适合用于路径搜索问题。

  2. 边界条件的处理

     • 对于不能到达的树，直接返回 -1。

  3. 复杂度分析

     • 时间复杂度：

       • 找树的位置：O(m * n)

       • 排序树的位置：O(k log k)，其中 k 是树的数量。

       • BFS 搜索：每次从起点到树的搜索复杂度为 O(m * n)。

     • 空间复杂度：O(m * n)，主要用于存储访问标记和队列。

  这种方法可以有效地解决树木砍伐的最小路径问题，确保路径的有效性和优化。