广度优先搜索 (BFS)⚓︎

广度优先搜索（ $\text{Breadth First Search}，\text{BFS}$ ）是一种用于遍历或搜索树或图的算法。它从根节点（或任意选定的起始节点）开始，沿着树的宽度遍历节点，先访问所有邻近节点，然后再逐层向下访问更深层次的节点。

$\text{BFS}$ 的基本步骤如下：

使用队列（Queue）来存储待访问的节点
从起始节点开始，将其标记为已访问并加入队列
重复以下步骤直到队列为空：
- 从队列中取出一个节点，访问该节点
- 将该节点的所有未访问过的邻近节点标记为已访问并加入队列
继续上述过程，直到所有可达节点都被访问

BFS

C++

vector<int> BFS(const vector<vector<int>> &graph, int start = 0) {
  int n = graph.size();
  vector<bool> visited(n, false);
  vector<int> distance(n, -1);  // 记录每个节点的深度

  queue<int> q;
  q.push(start);  // 从start节点开始入队
  visited[start] = true;
  int depth      = 0;

  while (!q.empty()) {
    int size = q.size();
    for (int i = 0; i < size; ++i) {
      int u = q.front();
      q.pop();
      distance[u] = depth;      // 记录节点u的深度
      for (int v : graph[u]) {  // 处理节点u
        if (!visited[v]) {
          visited[v] = true;
          q.push(v);  // 邻接点入队
        }
      }
    }
    ++depth;  // 深度增加
  }
  return distance;
}

0-1 BFS⚓︎

在某些图中，边的权重只有两种可能值（通常是 $0$ 和 $1$ ）。对于这种情况，可以使用一种称为 $\text{0-1 BFS}$ 的特殊算法来高效地找到从起始节点到所有其他节点的最短路径。

$\text{0-1 BFS}$ 的基本思想是使用双端队列（ $\text{Deque}$ ）来存储待访问的节点。对于每条边，如果其权重为 $0$ ，则将其终点添加到队列的前端；如果权重为 $1$ ，则将其终点添加到队列的后端。这样可以确保在处理节点时，总是优先处理权重较小的边。

这样做的好处是， $\text{0-1 BFS}$ 可以在 $O(V + E)$ 的时间复杂度内找到最短路径，其中 $V$ 是节点数， $E$ 是边数。这比传统的 $\text{Dijkstra}$ 算法在处理只有两种权重的图时更高效。

到达角落需要移除障碍物的最小数目

给定一个二维网格 $grid$ ，其中 $0$ 表示空地， $1$ 表示障碍物。你可以从一个格子移动到其相邻的上、下、左、右四个格子。你需要找到从左上角 $(0, 0)$ 到右下角 $(m-1, n-1)$ 的路径上需要移除的障碍物的最小数目。

C++

#include <deque>
#include <vector>
using namespace std;

class Solution {
 public:
  int minimumObstacles(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    array<pair<int, int>, 4> directions = {
        {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
    };
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    using TIII = tuple<int, int, int>;  // (x, y, obstacles)
    deque<TIII> dq;
    dq.emplace_back(0, 0, 0);
    visited[0][0] = true;

    while (!dq.empty()) {
      auto [x, y, obstacles] = dq.front();
      dq.pop_front();
      if (x == m - 1 && y == n - 1) { return obstacles; }
      for (auto &[dx, dy] : directions) {
        int nx = x + dx, ny = y + dy;
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
          visited[nx][ny] = true;
          if (grid[nx][ny] == 1) {  // 障碍物
            dq.emplace_back(nx, ny, obstacles + 1);
          } else {
            dq.emplace_front(nx, ny, obstacles);
          }
        }
      }
    }
    return -1;
  }
};

网格传送门旅游

给定一个 $m \times n$ 的二维网格 $matrix$ ，每个格子包含一个字符，可能是大写字母（表示传送门）或 $\#$ （表示障碍物）。你可以从左上角 $(0, 0)$ 出发，目标是到达右下角 $(m-1, n-1)$ 。你可以向上、下、左、右移动到相邻的格子，或者使用传送门将你传送到相同字母的格子。每次移动到相邻格子需要 $1$ 步，而使用传送门不需要任何步数，每种传送门只能使用一次。请返回从起点到终点的最少步数，如果无法到达则返回 $-1$ 。

传送门

将二维网格中的每个格子视为图中的一个节点。所有相同字母（传送门）之间都有一条边权为 $0$ 的边，所有相邻格子之间都有一条边权为 $1$ 的边。

传送门只能使用一次，因此需要一个额外的数组来记录每个传送门是否已经被使用过（或者使用传送门之后将该传送门对应的所有节点从图中删除）。

C++

#include <deque>
#include <vector>
using namespace std;

class Solution {
 public:
  int minMoves(vector<string> &matrix) {
    int m = matrix.size(), n = matrix[0].size();
    if (matrix[0][0] == '#') { return -1; }

    using PII                = pair<int, int>;
    array<PII, 4> directions = {
        {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
    };

    vector<vector<PII>> portals(26);  // 传送门位置
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (matrix[i][j] >= 'A' && matrix[i][j] <= 'Z') {
          portals[matrix[i][j] - 'A'].emplace_back(i, j);
        }
      }
    }

    vector<vector<int>> distance(m, vector<int>(n, INT_MAX));

    deque<PII> dq;  // (x, y)
    dq.emplace_back(0, 0);

    distance[0][0] = 0;
    while (!dq.empty()) {
      auto [x, y] = dq.front();
      dq.pop_front();
      if (x == m - 1 && y == n - 1) { return distance[x][y]; }

      // 传送门
      if (matrix[x][y] >= 'A' && matrix[x][y] <= 'Z') {
        int p = matrix[x][y] - 'A';
        for (auto &[px, py] : portals[p]) {
          if (px == x && py == y) { continue; }
          if (distance[px][py] > distance[x][y]) {
            distance[px][py] = distance[x][y];  // 传送，距离不变
            dq.emplace_front(px, py);
          }
        }
        portals[p].clear();  // 防止重复传送
      }

      for (auto &[dx, dy] : directions) {
        int nx = x + dx, ny = y + dy;
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] != '#') {
          if (distance[nx][ny] > distance[x][y] + 1) {  // 更新距离
            distance[nx][ny] = distance[x][y] + 1;      // 普通移动，距离+1
            dq.emplace_back(nx, ny);
          }
        }
      }
    }
    return -1;
  }
};

双向 BFS⚓︎

双向 $\text{BFS}$ 是一种优化的广度优先搜索算法，适用于在无权图中寻找两个节点之间的最短路径。与传统的 $\text{BFS}$ 从起始节点开始向外扩展不同，双向 $\text{BFS}$ 同时从起始节点和目标节点开始搜索，直到两次搜索相遇。

双向 $\text{BFS}$ 的好处在于它可以显著减少搜索空间，从而提高搜索效率。因为每次搜索的深度只有原来的一半，所以在大多数情况下，双向 $\text{BFS}$ 的时间复杂度为 $O(b^{d/2})$ ，其中 $b$ 是每个节点的平均分支因子， $d$ 是起始节点和目标节点之间的距离。

双向 $\text{BFS}$ 的核心思想和 $\text{Meet in the Middle}$ 相似，都是通过将问题分解为两个较小的子问题来提高效率。双向 $\text{BFS}$ 主要用于图的最短路径问题， $\text{Meet in the Middle}$ 主要用于组合问题（如子集和问题）。

单词接龙

给定两个单词（ $\text{beginWord}$ 和 $\text{endWord}$ ）和一个字典 $\text{wordList}$ ，找出从 $\text{beginWord}$ 到 $\text{endWord}$ 的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母。
转换后的单词必须是字典中的单词。
注意： $\text{beginWord}$ 不需要在字典中。

C++

#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
 public:
  int ladderLength(string beginWord, string endWord, vector<string> &wordList) {
    unordered_set<string> wordSet(wordList.begin(), wordList.end());
    if (wordSet.find(endWord) == wordSet.end()) { return 0; }

    unordered_set<string> small{beginWord};  // 从beginWord开始搜索（小集合）
    unordered_set<string> large{endWord};    // 从endWord开始搜索（大集合）
    unordered_set<string> next;              // 下一层节点

    int step = 1;
    while (!small.empty() && !large.empty()) {
      if (small.size() > large.size()) { swap(small, large); }  // 保持small是较小的集合
      for (const string &word : small) { wordSet.erase(word); }  // 移除已访问的单词
      for (const string &word : small) {
        string curr = word;
        // 枚举所有可能的单词
        for (int i = 0; i < curr.size(); ++i) {
          char original = curr[i];
          for (char c = 'a'; c <= 'z'; ++c) {
            if (c == original) { continue; }
            curr[i] = c;
            if (large.find(curr) != large.end()) { return step + 1; }
            if (wordSet.find(curr) != wordSet.end()) { next.insert(curr); }
          }
          curr[i] = original;
        }
      }

      swap(small, next);
      next.clear();
      ++step;
    }
    return 0;
  }
};

广度优先搜索 (BFS)⚓︎

0-1 BFS⚓︎

双向 BFS⚓︎

评论