跳转至

# BFS（搜索）

## 引入

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

## 解释

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

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

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

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

## 例题

例题 Luogu B3625 迷宫寻路

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

解答

实现时需要维护一个队列来存储待处理的坐标，并配合访问标记数组避免重复计算．一个结点扩展可到达结点的时候，需要向上下左右拓展，这四个方向分别为 (𝑥,𝑦 +1)(x,y+1)，(𝑥,𝑦 −1)(x,y−1)，(𝑥 +1,𝑦)(x+1,y)，(𝑥 −1,𝑦)(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 1 和 𝑛 n 之间，相应的操作就无法进行．问：从第 𝑎 a 楼到第 𝑏 b 楼至少操作几次电梯？如果无法到达，输出 −1−1．

解答

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

代码中，直接记录距离数组，并利用距离是否为默认值（即 −1−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;
    }

## 习题

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

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, Anguei, c-forrest, vincent-163, ChungZH, Enter-tainer, ksyx, ouuan, Qlgdgasdx, Tiphereth-A, TrisolarisHD, Xeonacid, ylxmf2005
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用