跳转至

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)\)，在代码中使用了方向数组。注意判断不能拓展到有障碍物的位置。

参考实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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\)）来判断结点是否尚未访问。

参考实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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;
}

习题

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用