02.BFS（搜索）

引入

BFS（广度优先搜索）为图论中的基础算法，详见 BFS（图论） 页面。在 搜索算法 中，该算法通常指利用队列结构逐层扩展状态的搜索方式，与图论中的 BFS 算法思想一致，特别适合求解 最短路径 或 最少步骤 类问题。

解释

BFS 的核心思想是 按层扩展，从起点开始逐层扫描可到达的位置。首次遇到终点时的路径长度即为最短路径。这种方式保证了搜索的层次性与最优性。

在实际执行中，BFS 会从起点出发，先访问起点的所有直接可到达结点，这些可到达结点构成了搜索的第一层；接着，再以这些可到达结点为新的起点，依次访问它们的邻居，形成第二层；以此类推，不断向外扩展，直至找到目标结点或遍历完所有可达结点。这个过程中，算法会借助队列和访问数组，将每一层新发现的结点（访问数组中还没有记录过的）依次入队，确保同一层的结点按照访问顺序依次被处理，从而严格遵循「按层扩展」的逻辑。

BFS 非常擅于快速求解 最短路径 或 最少步骤。当算法在某一层首次遇到目标时，此时经过的路径长度（步骤数）必然是最短的。这是因为 BFS 算法的「按层扩展」机制保证了每个结点都是通过最少的步数被访问到：就像从起点出发，沿着最直接的路径不断搜索，直到抵达终点，不会出现绕路或走多余步骤的情况。在这类问题中，BFS 通常也比 DFS 的效率更高。

但是，相较于 DFS，BFS 也有其缺点。通常情况下，BFS 需要更大的内存，缺乏天然的回溯过程，且深度剪枝相对没有 DFS 灵活。

例题

例题 Luogu B3625 迷宫寻路

在一个 $n\times m$ 的迷宫矩阵中，. 表示可通行区域，# 表示障碍物。从起点 $(1,1)$ 出发，每次可向上下左右四个方向移动，问是否能到达终点 $(n,m)$。

解答

实现时需要维护一个队列来存储待处理的坐标，并配合访问标记数组避免重复计算。一个结点扩展可到达结点的时候，需要向上下左右拓展，这四个方向分别为 $(x,y+1)$，$(x,y-1)$，$(x+1,y)$，$(x-1,y)$，在代码中使用了方向数组。注意判断不能拓展到有障碍物的位置。

参考实现

#include <iostream>
#include <queue>
using namespace std;
 
char a[110][110];    // 存储迷宫地图
bool vis[110][110];  // 记录访问状态
int n, m;            // 迷宫尺寸
 
struct node {
  int x, y;
};  // 定义坐标结构体
 
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};  // 方向数组（右左上下）
 
// 检查坐标是否合法
bool chk(int x, int y) {
  return (x >= 1 && x <= n && y >= 1 && y <= m  // 边界检查
          && !vis[x][y]                         // 未访问过
          && a[x][y] != '#');                   // 不是障碍物
}
 
bool bfs() {
  queue<node> q;
  q.push({1, 1});  // 起点入队
  vis[1][1] = 1;   // 标记起点已访问
  while (!q.empty()) {
    node p = q.front();  // 取出队首坐标
    q.pop();
    int px = p.x, py = p.y;
    if (px == n && py == m) return true;  // 到达终点立即返回
    // 向四个方向扩展
    for (int i = 0; i < 4; ++i) {
      int nx = px + dx[i], ny = py + dy[i];
      if (chk(nx, ny)) {   // 合法性检查
        q.push({nx, ny});  // 新坐标入队
        vis[nx][ny] = 1;   // 标记已访问
      }
    }
  }
  return false;
}
 
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) cin >> a[i][j];
  cout << (bfs() ? "Yes" : "No") << endl;
  return 0;
}

例题 Luogu P1135 奇怪的电梯

有 $n$ 层楼和一架电梯。电梯位于第 $i$ 层楼时，向上或向下移动的层数等于一个固定的数字 $k_i$。如果到达的层数不合法，即不在 $1$ 和 $n$ 之间，相应的操作就无法进行。问：从第 $a$ 楼到第 $b$ 楼至少操作几次电梯？如果无法到达，输出 $-1$。

解答

本题需要计算最短路径，这正是 BFS 擅长解决的问题。实现时，需要在队列中同时维护需要处理的楼层位置和从起点 $a$ 出发到达当前楼层的最短距离，并配合访问标记数组避免重复加入同一个元素。一个结点 $i$ 扩展可到达结点的时候，需要向 $i+k_i$ 和 $i-k_i$ 扩展，注意不能到达非法楼层。当扩展到尚未到达的合法楼层时，需要将它加入队列，并记录到达该楼层的最短距离为到达当前所在楼层的最短距离加一。当首次到达结点 $b$ 时，记录的最短距离就是最终答案。

代码中，直接记录距离数组，并利用距离是否为默认值（即 $-1$）来判断结点是否尚未访问。

参考实现

#include <iostream>
#include <queue>
using namespace std;
const int N = 210;
int n, a, b, k[N], d[N];
 
int main() {
  cin >> n >> a >> b;
  for (int i = 1; i <= n; ++i) cin >> k[i];
  for (int i = 1; i <= n; ++i) d[i] = -1;
  queue<int> q;
  d[a] = 0;
  q.push(a);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    if (x == b) {
      break;
    }
    int y = x + k[x];
    if (y <= n && d[y] == -1) {
      d[y] = d[x] + 1;
      q.push(y);
    }
    y = x - k[x];
    if (y >= 1 && d[y] == -1) {
      d[y] = d[x] + 1;
      q.push(y);
    }
  }
  cout << d[b] << endl;
  return 0;
}

习题

• Luogu P1443 马的遍历
• Luogu P3956 [NOIP 2017 普及组] 棋盘
• Luogu P1126 机器人搬重物