广度优先搜索

如果把图遍历比作探索一座陌生城市，深度优先搜索（DFS）像是一个执着地"一条路走到底、走不通再回头"的探险者，而广度优先搜索（Breadth-First Search，BFS）更像是投入湖面的石子激起的涟漪——从落点出发，一圈一圈匀速向外扩散，先抵达近处，再抵达远处。这种"层层向外"的推进方式，让 BFS 在所有"距离敏感"的场景中拥有无可替代的地位：它天然按距离从近到远访问节点，因此在无权图（或等权图）中，第一次到达某点所走的路径就是最短路径。

本文是搜索算法系列的第二篇，与 DFS 专篇 形成"双璧对照"。我们将从 FIFO 队列与分层性质出发，严格证明 BFS 的最短路保证，再用一套通用模板覆盖图与网格两种形态；随后逐个展开树层序、网格最短路、多源 BFS、0-1 BFS、双向 BFS 与 A* 等变体，最后在横向对比中厘清 BFS 与 DFS 的分工口诀。

为什么需要广度优先搜索：动机与起源

从一个具体场景切入。给你一个网格迷宫，'.' 是通路，'#' 是墙，求从左上角到右下角的最少步数。如果用 DFS 思路：它会沿一条路深挖到底，撞墙才回头，找到终点时记录步数，然后继续找其他路径，最后取最小——这要求枚举所有可能的路径，数量是指数级的。

但仔细想想：我们其实不需要"所有路径"，只需要"最短的那条"。如果有一种搜索方式能保证"先搜到近处、再搜到远处"，那么第一次到达终点时就可以立即停手——因为后续找到的路径只会更长。这正是 BFS 的核心动机：利用"层层向外扩"的性质，让距离为 $d$ 的节点先于距离为 $d+1$ 的节点被处理。

BFS 的动机不限于迷宫。以下场景都是它的天然战场：

• 最少操作次数：八数码、魔方、转盘锁——每次操作等价于走一条边，求最少操作就是无权图最短路。
• 最近可达状态：从初始状态出发，最少几步能到达目标状态。
• 层序扩散：社交网络中"几度好友"、疾病传播范围、火灾蔓延模拟——天然按层展开。
• 公平性：BFS 保证先发现的节点距离更近，这一"公平"特性是队列先进先出（FIFO）的直接产物。

与 DFS 的分工也由此清晰：DFS 擅长"找可行解 / 枚举所有解"（见 回溯算法），BFS 擅长"求最短 / 最少 / 最近"。两者并非对立，而是互补。

BFS 的代价在于空间。DFS 的空间是递归栈深度 $O(D)$，而 BFS 的队列可能存满一整层节点，最坏 $O(W)$（$W$ 是图的最大宽度）。当答案深度大、分支因子大时，BFS 的队列会爆炸——这正是后续"双向 BFS""A*"等优化的动机。

核心思想：FIFO 队列与层序推进

分层性质与层序推进

BFS 的唯一数据结构是一个先进先出（FIFO）的队列。它的不变式是：队列里的节点始终按"距离不减"排列——队首距离 $\le$ 队尾距离。这一性质由两个动作共同保证：取队首扩展、邻居入队即标记。

分层（level-by-level）展开：第 0 层是起点（距离 0），第 $k$ 层是距离起点为 $k$ 的所有节点。BFS 严格地"处理完第 $k$ 层，才进入第 $k+1$ 层"。

         起点 A              L0 (距离 0)
        /     \
       B       C             L1 (距离 1)
      / \     / \
     D   E   F   G           L2 (距离 2)
      \   \ /   /
       \   H   /             L3 (距离 3)
        \ | | /
          I

处理顺序: A → B,C → D,E,F,G → H,I
同一层的节点距离相同，BFS 按层依次处理

层间边界如何划分？最常用的技巧是"size 法"：每轮开始时记录 q.size()，这一数量恰好是当前层的节点数，用一层 for 循环把它们全部取出，就完成了一层的处理。这个技巧在树层序、网格分层、多源扩散中反复用到。

图:  A -- B -- D
      \    \
       C    E

第 0 步: 入队 A            队列: [A]      dist: A=0
第 1 步: 出队 A, 入队 B,C  队列: [B,C]    dist: B=1, C=1
第 2 步: 出队 B, 入队 D,E  队列: [C,D,E]  dist: D=2, E=2
第 3 步: 出队 C            队列: [D,E]
第 4 步: 出队 D            队列: [E]
第 5 步: 出队 E            队列: []

FIFO 保证先入队的先扩展，从而维持层序

正确性证明：BFS 为何给出无权图最短路

命题：BFS 首次访问某节点 $u$ 时，经过的边数 $\text{dist}[u]$ 就是 $u$ 到起点的最短距离。

证明（对层号 $d$ 做归纳）：

• 基础：$d=0$，起点距离 0，显然最短。
• 归纳：假设所有 $d \le k$ 层的节点首次访问即最短。考虑第 $k+1$ 层的节点 $v$，它由某个第 $k$ 层节点 $u$ 扩展而来，$\text{dist}[v] = \text{dist}[u] + 1 = k+1$。反设存在更短路径 $\text{dist}'(v) < k+1$，则该路径上 $v$ 的前驱 $w$ 满足 $\text{dist}'(w) = \text{dist}'(v) - 1 \le k-1 < k$。但 $w$ 若距离 $\le k$，按归纳假设 BFS 早已在 $\le k$ 层处理过 $w$，于是 $v$ 会在第 $\text{dist}'(w)+1 \le k$ 层就被发现，与 $v$ 在第 $k+1$ 层首次发现矛盾。

关键引理：队列中节点的距离单调不减（队首 $\le$ 队尾）。这是 FIFO + "入队时标记"的直接结果——只有当前层的节点才能把邻居（下一层）入队，而当前层处理完后队列里只剩下下一层，距离严格更大。

推论：BFS 终止时，dist 数组即为各点到起点的最短距离。若某点 dist 为 -1（未访问），则不可达。

这个证明揭示了 BFS 高效的根源：它不需要像 DFS 那样枚举所有路径再取最小，因为"层序"本身就是按距离排序的，第一次到达即最优。

通用 BFS 模板

图的 BFS（邻接表）

#include <vector>
#include <queue>

// 图的 BFS 模板（邻接表）
// adj: 邻接表；start: 起点；visited: 访问标记
void bfs(const std::vector<std::vector<int>>& adj,
         int start, std::vector<bool>& visited) {
  std::queue<int> q;
  q.push(start);
  visited[start] = true;            // 入队时立即标记
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    // 前序动作：在此处理 u（如记录距离）
    for (int v : adj[u]) {
      if (visited[v]) continue;     // 已访问则跳过
      visited[v] = true;            // 入队时标记
      q.push(v);
    }
  }
}

网格 BFS（方向数组）

网格是"伪装成矩阵的图"：每格是一节点，上下左右四邻接为边。方向数组 dx/dy 把四个方向的位移封装成一对数组，循环展开即可。

            (x-1, y)
               ↑
               |
  (x,y-1) ← (x,y) → (x,y+1)
               |
               ↓
            (x+1, y)

dx = {0, 0, 1, -1}   // 行变化：右、左、下、上
dy = {1, -1, 0, 0}   // 列变化：右、左、下、上

#include <vector>
#include <queue>

// 网格 BFS 模板（四方向）
void gridBFS(
    const std::vector<std::vector<char>>& grid,
    int sx, int sy) {
  int m = grid.size(), n = grid[0].size();
  const int dx[4] = {0, 0, 1, -1};
  const int dy[4] = {1, -1, 0, 0};
  std::vector<std::vector<bool>> vis(m,
      std::vector<bool>(n, false));
  std::queue<std::pair<int,int>> q;
  q.push({sx, sy});
  vis[sx][sy] = true;               // 入队即标记
  while (!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    for (int i = 0; i < 4; ++i) {
      int nx = x + dx[i], ny = y + dy[i];
      if (nx < 0 || nx >= m) continue;
      if (ny < 0 || ny >= n) continue;
      if (grid[nx][ny] == '#') continue;  // 障碍
      if (vis[nx][ny]) continue;
      vis[nx][ny] = true;           // 入队即标记
      q.push({nx, ny});
    }
  }
}

需要八连通（允许对角线移动）时，把方向数组扩展到 8 个：

const int dx[8] = {0,0,1,-1,1,1,-1,-1};
const int dy[8] = {1,-1,0,0,1,-1,1,-1};

关键细节：入队时标记 vs 出队时标记

这是 BFS 最容易写错、也最影响性能的细节。

正确做法：入队时立即标记 visited。 一个节点只会在首次被发现时入队一次，队列规模严格 $O(V)$。

错误做法：出队时才标记。 会导致一个节点被多个前驱重复入队，队列膨胀。最坏情况下总工作量从 $O(V+E)$ 退化到 $O(VE)$（队列峰值可达 $O(E)$，总处理量可达 $O(VE)$），直接 TLE/MLE。

对比两种写法在链状图 A-B-C-D 上的表现：出队标记时，B 会被 A 入队一次，但 A 出队前 C 可能也被某路径入队……链越长、图越宽，重复入队越严重。而入队标记从源头杜绝了重复。

这一原理与 DFS 的 visited 标记一致（详见 DFS 专篇 的访问标记章节），但 BFS 的重复入队危害更隐蔽——DFS 顶多多递归几次，BFS 则会让队列指数膨胀，直到内存耗尽。

无权图最短路径与最小步数

这是 BFS 最核心的应用场景，也是它区别于 DFS 的最大价值所在。

通用框架

• dist 数组：记录起点到各点最短距离，初始化为 -1（未访问），起点为 0。用 -1 而非 0 表示未访问，是因为 0 是起点的合法距离。
• BFS 主循环：出队 $u$，遍历邻居 $v$，若 dist[v] == -1 则 dist[v] = dist[u] + 1 并入队。
• 终止：队空。dist[终点] 即为答案，-1 表示不可达。
• 复杂度：时间 $O(V+E)$，空间 $O(V)$。

经典例题：迷宫最短步数

在 $m \times n$ 网格迷宫中，'.' 是通路、'#' 是墙，求从 $(sx, sy)$ 到 $(tx, ty)$ 的最少步数，不可达返回 -1。

思路。每个格子是节点，四方向移动是边，所有边权重都是 1（一步），求最少步数即无权图最短路。BFS 第一次到达终点时 dist 就是最短步数，可以立即返回。

#include <vector>
#include <queue>
#include <string>

// 迷宫最短步数：从 (sx,sy) 到 (tx,ty) 的最少步数
// '.' 可走，'#' 障碍；不可达返回 -1
int mazeBFS(const std::vector<std::string>& maze,
            int sx, int sy, int tx, int ty) {
  int m = maze.size(), n = maze[0].size();
  const int dx[4] = {0, 0, 1, -1};
  const int dy[4] = {1, -1, 0, 0};
  std::vector<std::vector<int>> dist(m,
      std::vector<int>(n, -1));       // -1 表示未访问
  std::queue<std::pair<int,int>> q;
  q.push({sx, sy});
  dist[sx][sy] = 0;                   // 起点距离 0
  while (!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    if (x == tx && y == ty)
      return dist[x][y];              // 到达终点
    for (int i = 0; i < 4; ++i) {
      int nx = x + dx[i], ny = y + dy[i];
      if (nx < 0 || nx >= m) continue;
      if (ny < 0 || ny >= n) continue;
      if (maze[nx][ny] == '#') continue;
      if (dist[nx][ny] != -1) continue;
      dist[nx][ny] = dist[x][y] + 1;  // 入队即标记
      q.push({nx, ny});
    }
  }
  return -1;                         // 不可达
}

逐段讲解：

• 初始化：dist 全填 -1，起点置 0 并入队。-1 兼任"未访问"标记，省去单独的 visited 数组。
• 出队与到达判断：每次出队检查是否为终点。由于 BFS 的层序性，第一次到达即为最短，直接返回。
• 方向扩展：四方向循环，依次检查越界、障碍、已访问，任一不满足则 continue。注意先判越界再访问 maze[nx][ny]，否则下标越界段错误。
• 入队即标记：dist[nx][ny] 在入队时赋值，保证不会重复入队。

复杂度。每个格子至多入队一次，每条边至多考察两次（无向），时间 $O(m \cdot n)$，空间 $O(m \cdot n)$。

方案回溯：还原一条最短路径

只求步数往往不够，有时要输出具体路径。做法是用一个 pre 数组记录每个节点的前驱，BFS 后从终点倒推回起点。

#include <vector>
#include <queue>
#include <algorithm>

// 用 pre 数组还原一条最短路径（图上 BFS）
// pre[v] = v 的前驱节点；起点 pre 为 -1
std::vector<int> shortestPath(
    const std::vector<std::vector<int>>& adj,
    int start, int target) {
  int n = adj.size();
  std::vector<int> pre(n, -1);
  std::vector<bool> vis(n, false);
  std::queue<int> q;
  q.push(start);
  vis[start] = true;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    if (u == target) break;
    for (int v : adj[u]) {
      if (vis[v]) continue;
      vis[v] = true;
      pre[v] = u;                    // 记录前驱
      q.push(v);
    }
  }
  if (!vis[target]) return {};       // 不可达
  std::vector<int> path;
  for (int cur = target; cur != -1; cur = pre[cur])
    path.push_back(cur);
  std::reverse(path.begin(), path.end());
  return path;
}

若要还原所有最短路径，pre 改成 vector<vector<int>>，每个节点记录所有可能在最短路上的前驱，BFS 后用 DFS 在前驱图上枚举所有路径。

状态空间 BFS

BFS 不限于显式图。把"状态"抽象成节点、"操作"抽象成边，任何"求最少操作次数"的问题都能套用 BFS。

典型例子是打开转盘锁（LeetCode 752）：四位数字锁 "0000"，每次可把某一位拧 +1 或 -1（循环到 9↔0），中途不能出现"死亡数字"，求到目标数字的最少拧动次数。状态是字符串 "1234"，操作是某一位 ±1，visited 用 unordered_set<string>。

#include <string>
#include <queue>
#include <unordered_set>

// 打开转盘锁：从 "0000" 到 target 的最少步数
// deadends 中的状态不可经过
int openLock(
    const std::vector<std::string>& deadends,
    const std::string& target) {
  std::unordered_set<std::string> dead(
      deadends.begin(), deadends.end());
  if (dead.count("0000")) return -1;
  if (target == "0000") return 0;
  std::queue<std::string> q;
  q.push("0000");
  dead.insert("0000");               // 入队即标记
  int steps = 0;
  while (!q.empty()) {
    ++steps;
    int size = q.size();
    for (int k = 0; k < size; ++k) {
      std::string cur = q.front();
      q.pop();
      for (int i = 0; i < 4; ++i) {  // 枚举每一位
        char old = cur[i];
        // +1 与 -1 两种操作
        for (int d : {1, -1}) {
          char c = (old - '0' + d + 10) % 10 + '0';
          cur[i] = c;
          if (cur == target) return steps;
          if (!dead.count(cur)) {
            dead.insert(cur);        // 入队即标记
            q.push(cur);
          }
          cur[i] = old;              // 恢复
        }
      }
    }
  }
  return -1;
}

关键点：状态用字符串编码，visited 用哈希集合。状态数上限是 $10^4$（四位数字），但加上操作约束后实际远小于此。这类"状态空间 BFS"的难点不在 BFS 本身，而在如何正确建模状态与转移——识别出问题具有"无权最短路"结构，是 BFS 建模的核心直觉。

树的层序遍历

二叉树的前序、中序、后序遍历以及深度相关计算（最大深度、路径总和）属于 DFS 专篇 的范畴，本文只讲层序遍历——按层横向展开，与 DFS 的纵向遍历形成互补。

树没有环，BFS 在树上退化为"层序遍历"，是 BFS 最直观的形态：不需要 visited（父节点唯一，只要不往回走即可），代码更简洁。

标准层序遍历

#include <vector>
#include <queue>

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x),
                    left(nullptr),
                    right(nullptr) {}
};

// 二叉树层序遍历（size 法分层）
std::vector<std::vector<int>> levelOrder(
    TreeNode* root) {
  std::vector<std::vector<int>> result;
  if (root == nullptr) return result;
  std::queue<TreeNode*> q;
  q.push(root);
  while (!q.empty()) {
    int size = q.size();              // 本层节点数
    std::vector<int> level;
    for (int i = 0; i < size; ++i) {
      TreeNode* node = q.front();
      q.pop();
      level.push_back(node->val);
      if (node->left) q.push(node->left);
      if (node->right) q.push(node->right);
    }
    result.push_back(level);
  }
  return result;
}

size 法分层是这一节的灵魂。int size = q.size() 在进入内层 for 之前快照当前层的节点数，内层循环恰好处理这一整层并把下一层全部入队。没有这一步，BFS 仍然正确（节点都会被访问），但无法按层分组收集结果。

锯齿形层序遍历（ZigZag）

奇数层从左到右、偶数层从右到左收集。用一个 bool 标志每层翻转方向，或者收集后 reverse。

#include <vector>
#include <queue>
// 复用上文 struct TreeNode 定义

// 锯齿形层序遍历（奇偶层交替方向）
std::vector<std::vector<int>> zigzagLevelOrder(
    TreeNode* root) {
  std::vector<std::vector<int>> result;
  if (root == nullptr) return result;
  std::queue<TreeNode*> q;
  q.push(root);
  bool leftToRight = true;            // 本层方向
  while (!q.empty()) {
    int size = q.size();
    std::vector<int> level(size);
    for (int i = 0; i < size; ++i) {
      TreeNode* node = q.front();
      q.pop();
      // 方向决定填入位置
      int idx = leftToRight ? i
                            : size - 1 - i;
      level[idx] = node->val;
      if (node->left) q.push(node->left);
      if (node->right) q.push(node->right);
    }
    result.push_back(level);
    leftToRight = !leftToRight;       // 翻转方向
  }
  return result;
}

这里没有用"收集后 reverse"的写法，而是在填入时就根据方向决定下标——leftToRight 时填 level[i]，否则填 level[size-1-i]。两种写法等价，但前者省一次 reverse。

右视图与层平均值

层序框架的变体只需微调收集逻辑：

• 右视图（LeetCode 199）：每层最后一个节点即为右视图可见节点。
• 层平均值（LeetCode 637）：每层累加求和再除以个数。
• 左视图：取每层首位。
• 层最大值（LeetCode 515）：每层遍历取 max。

#include <vector>
#include <queue>

// 复用上文 struct TreeNode 定义
// 二叉树右视图：每层最后一个节点
std::vector<int> rightSideView(TreeNode* root) {
  std::vector<int> result;
  if (root == nullptr) return result;
  std::queue<TreeNode*> q;
  q.push(root);
  while (!q.empty()) {
    int size = q.size();
    for (int i = 0; i < size; ++i) {
      TreeNode* node = q.front();
      q.pop();
      if (i == size - 1)              // 本层最后一个
        result.push_back(node->val);
      if (node->left) q.push(node->left);
      if (node->right) q.push(node->right);
    }
  }
  return result;
}

这一节巩固了"size 法分层"的模板写法，它在后续网格 BFS 的多源扩散中还会反复用到。

网格 BFS 进阶

网格是 BFS 的高频战场。需要先厘清分工：网格连通性问题（岛屿数量、洪泛填充）应优先用 DFS 专篇 的 DFS 洪泛，而网格最短步数才用 BFS。本节覆盖三个进阶模式：字符串变换建模、多源 BFS、DFS+BFS 混合搜索。

示例：单词接龙

给定 beginWord、endWord 和词典 wordList，每次变换一个字母，中间词必须在词典中，求最短变换序列长度。

建模：每个单词是节点，可变换一个字母得到的单词是邻居，BFS 求最短路。难点在高效建边——$N$ 个单词两两比较是 $O(N^2 L)$，太慢。

优化建边：用"通配符中间状态"。对每个单词 hit，生成 *it、h*t、hi* 三个通配形式，把它们作为中间节点连边。建图复杂度降到 $O(N L^2)$，BFS 时邻居通过通配符间接发现。

#include <vector>
#include <string>
#include <queue>
#include <unordered_set>
#include <unordered_map>

// 单词接龙：通配符建图 + BFS
int ladderLength(const std::string& beginWord,
                 const std::string& endWord,
                 std::vector<std::string>& wordList) {
  std::unordered_set<std::string> dict(
      wordList.begin(), wordList.end());
  if (!dict.count(endWord)) return 0;
  // 通配符 -> 能匹配的单词列表
  std::unordered_map<std::string,
      std::vector<std::string>> pattern;
  int L = beginWord.size();
  for (const std::string& w : wordList) {
    for (int i = 0; i < L; ++i) {
      std::string p = w;
      p[i] = '*';
      pattern[p].push_back(w);
    }
  }
  std::queue<std::string> q;
  std::unordered_set<std::string> vis;
  q.push(beginWord);
  vis.insert(beginWord);             // 入队即标记
  int steps = 1;
  while (!q.empty()) {
    int size = q.size();
    ++steps;
    for (int k = 0; k < size; ++k) {
      std::string w = q.front();
      q.pop();
      for (int i = 0; i < L; ++i) {
        std::string p = w;
        p[i] = '*';
        for (const std::string& nb : pattern[p]) {
          if (nb == endWord) return steps;
          if (!vis.count(nb)) {
            vis.insert(nb);          // 入队即标记
            q.push(nb);
          }
        }
      }
    }
  }
  return 0;
}

复杂度。建图 $O(N L^2)$，BFS 每个单词至多入队一次，每次扩展 $O(L^2)$ 个邻居，总计 $O(N L^2)$。远优于朴素 $O(N^2 L)$ 建边。

多源 BFS：腐烂的橘子

网格中每个格子是空（0）、好橘子（1）或腐烂橘子（2）。每分钟腐烂橘子会把四方向相邻的好橘子传染。求所有橘子腐烂的最少分钟数，若有好橘子永远无法被感染则返回 -1。

核心技巧：把所有初始腐烂橘子同时入队，再普通 BFS。这等价于添加一个"超级源点"连到所有初始腐烂橘子，把多源问题归约为单源。

初始:          第 1 分钟:      第 2 分钟:
. . . . .      . . . . .      . 2 . . .
. . 2 . .      . 2 2 2 .      2 2 2 2 .
. . . . .      . . 2 . .      . 2 2 2 .
. . . . .      . . . . .      . . 2 . .

2 = 初始源点，数字 1/2 表示在第几分钟被感染
多源同时入队 = 一个超级源点的单源 BFS

为什么多源等价于超级源点：想象一个虚拟节点 $S$ 连到所有初始腐烂橘子，边权为 1。从 $S$ 出发 BFS，第一层就是所有初始源点（距离 1），第二层是它们传染的第一批（距离 2）……每个格子被感染的时间 = 到 $S$ 的距离 - 1。由于所有初始源点同时入队且距离相同（都是 0），直接多源入队就等价于从超级源点出发，无需真正建出 $S$。

#include <vector>
#include <queue>

// 腐烂的橘子：多源 BFS
// 返回所有橘子腐烂的最少分钟数；不可达返回 -1
int orangesRotting(
    std::vector<std::vector<int>>& grid) {
  int m = grid.size(), n = grid[0].size();
  const int dx[4] = {0, 0, 1, -1};
  const int dy[4] = {1, -1, 0, 0};
  std::queue<std::pair<int,int>> q;
  int fresh = 0;
  // 所有初始腐烂橘子同时入队（多源）
  for (int i = 0; i < m; ++i)
    for (int j = 0; j < n; ++j) {
      if (grid[i][j] == 2) q.push({i, j});
      else if (grid[i][j] == 1) ++fresh;
    }
  int minutes = 0;
  while (!q.empty() && fresh > 0) {
    int size = q.size();
    ++minutes;
    for (int k = 0; k < size; ++k) {
      int x = q.front().first;
      int y = q.front().second;
      q.pop();
      for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx >= m) continue;
        if (ny < 0 || ny >= n) continue;
        if (grid[nx][ny] != 1) continue;  // 只感染好橘子
        grid[nx][ny] = 2;          // 入队即标记
        q.push({nx, ny});
        --fresh;                   // 好橘子减一
      }
    }
  }
  return fresh == 0 ? minutes : -1;
}

细节。fresh > 0 作为循环条件：一旦没有好橘子就停止，避免多余的一轮扩展。grid 原地修改（好橘子变腐烂）兼任 visited，省额外空间。答案就是 minutes，因为每轮 ++minutes 对应"再过一分钟"。

同类问题：墙与门（LeetCode 286，多源 BFS 从所有门出发填最近距离）、火势蔓延模拟、太平洋大西洋水流（反向 BFS 从边界出发）。识别"多源同时扩散"是关键。

示例：最短桥

在 $n \times n$ 的 0-1 矩阵中，恰好有两座由 1 连成的岛（四连通），求把它们连成一座岛所需翻转的最少 0 的个数（即两岛之间的最短桥）。

思路。这道题是 DFS 与 BFS 配合的范例：

1. 先用 DFS（或 BFS）标记第一座岛的所有格子（改成 2），并把它们全部入队。
2. 再从这些格子做多源 BFS，向水面（0）扩展，第一次碰到另一座岛（仍为 1）时的步数就是最短桥。

#include <vector>
#include <queue>
#include <functional>

// 最短桥：DFS 标记第一座岛 + BFS 找最短桥
int shortestBridge(
    std::vector<std::vector<int>>& grid) {
  int m = grid.size(), n = grid[0].size();
  const int dx[4] = {0, 0, 1, -1};
  const int dy[4] = {1, -1, 0, 0};
  std::queue<std::pair<int,int>> q;

  // DFS 标记第一座岛（1 → 2），并入队
  std::function<void(int,int)> dfs =
      [&](int x, int y) {
    if (x < 0 || x >= m || y < 0 || y >= n)
      return;
    if (grid[x][y] != 1) return;
    grid[x][y] = 2;                  // 标记为已访问
    q.push({x, y});                  // 入队作为 BFS 源
    for (int i = 0; i < 4; ++i)
      dfs(x + dx[i], y + dy[i]);
  };

  bool found = false;
  for (int i = 0; i < m && !found; ++i)
    for (int j = 0; j < n && !found; ++j)
      if (grid[i][j] == 1) {
        dfs(i, j);                   // 标记整座岛
        found = true;
      }

  // 多源 BFS 找到第二座岛（仍为 1）的最短距离
  int dist = 0;
  while (!q.empty()) {
    int size = q.size();
    for (int k = 0; k < size; ++k) {
      int x = q.front().first;
      int y = q.front().second;
      q.pop();
      for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx >= m) continue;
        if (ny < 0 || ny >= n) continue;
        if (grid[nx][ny] == 2) continue;  // 已访问
        if (grid[nx][ny] == 1)
          return dist;              // 到达第二座岛
        grid[nx][ny] = 2;           // 标记水面已访问
        q.push({nx, ny});
      }
    }
    ++dist;
  }
  return -1;
}

为什么用 DFS 标记、BFS 扩展。DFS 擅长"把一个连通块一次性标完"（见 DFS 专篇 的网格洪泛），BFS 擅长"求最短距离"。两者分工：DFS 解决"哪些格子属于第一座岛"，BFS 解决"从这些格子出发到第二座岛的最短步数"。这种混合搜索在竞赛中很常见。

复杂度。DFS 标记 $O(m \cdot n)$，BFS 扩展 $O(m \cdot n)$，总计 $O(m \cdot n)$。

双端队列 BFS（0-1 BFS）

当边权只有 0 和 1 时，普通 BFS 失效（权 0 的边不该让距离 +1），Dijkstra 又杀鸡用牛刀。0-1 BFS 用双端队列 deque 巧妙解决。

原理

核心技巧：权 0 的边把邻居 push_front（不增加距离，同层优先），权 1 的边把邻居 push_back（增加距离，下一层）。这样 deque 始终维持"距离单调不减"的不变式——队首始终是当前距离最小的节点，等价于对 0/1 权的特殊 Dijkstra，但复杂度是线性的 $O(V+E)$。

        队首                队尾
         ↓                   ↓
deque: [ u | v | w | ... | z ]

权 0 边 → push_front (插队首, 同层, 距离不变)
权 1 边 → push_back  (排队尾, 下一层, 距离+1)

不变式: 队首始终是当前距离最小的节点
        deque 中距离单调不减

与普通 BFS 的关系：若所有边权都为 1，0-1 BFS 退化回普通 BFS（只 push_back）。与 Dijkstra 的关系：0-1 BFS 是 Dijkstra 在权值仅为 0/1 时的线性时间特例（$O(V+E)$ vs $O((V+E)\log V)$）。

模板

#include <vector>
#include <deque>
#include <climits>

// 0-1 BFS：边权只有 0 和 1 的单源最短路
// adj[u] = {(邻居 v, 权重 w)}，w 为 0 或 1
std::vector<int> bfs01(
    const std::vector<std::vector<std::pair<int,int>>>& adj,
    int start) {
  int n = adj.size();
  std::vector<int> dist(n, INT_MAX);
  std::deque<int> dq;
  dq.push_back(start);
  dist[start] = 0;
  while (!dq.empty()) {
    int u = dq.front();
    dq.pop_front();
    for (const auto& edge : adj[u]) {
      int v = edge.first;
      int w = edge.second;
      if (dist[u] + w < dist[v]) {   // 松弛
        dist[v] = dist[u] + w;
        if (w == 0)
          dq.push_front(v);          // 权 0：同层
        else
          dq.push_back(v);           // 权 1：下一层
      }
    }
  }
  return dist;
}

陷阱：与普通 BFS 不同，0-1 BFS 中节点可能因更优距离被重新入队（松弛成功就再入队一次），不能简单地"访问过就跳过"。这是 dist[u] + w < dist[v] 这一松弛条件的直接结果，与 Dijkstra 的松弛逻辑一致。

经典例题：0-1 矩阵

给定 $m \times n$ 的 0-1 矩阵，求每个格子到最近的 0 的距离。

建模：从所有 0 出发做多源 BFS，每扩展一步距离 +1。这其实不需要 0-1 BFS（普通多源 BFS 即可），但若把"移动到相邻格"看成权 1 的边，它与 0-1 BFS 同构。这里用它演示多源 BFS 的等价性。

#include <vector>
#include <queue>

// 0-1 矩阵：每个格子到最近 0 的距离（多源 BFS）
std::vector<std::vector<int>> updateMatrix(
    std::vector<std::vector<int>>& mat) {
  int m = mat.size(), n = mat[0].size();
  const int dx[4] = {0, 0, 1, -1};
  const int dy[4] = {1, -1, 0, 0};
  std::vector<std::vector<int>> dist(m,
      std::vector<int>(n, -1));
  std::queue<std::pair<int,int>> q;
  // 所有 0 入队（多源），距离为 0
  for (int i = 0; i < m; ++i)
    for (int j = 0; j < n; ++j)
      if (mat[i][j] == 0) {
        q.push({i, j});
        dist[i][j] = 0;
      }
  while (!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    for (int i = 0; i < 4; ++i) {
      int nx = x + dx[i], ny = y + dy[i];
      if (nx < 0 || nx >= m) continue;
      if (ny < 0 || ny >= n) continue;
      if (dist[nx][ny] != -1) continue;
      dist[nx][ny] = dist[x][y] + 1;
      q.push({nx, ny});
    }
  }
  return dist;
}

关键反转：朴素思路是从每个 1 出发 BFS 找最近的 0，复杂度 $O((m \cdot n)^2)$。反转方向——从所有 0 出发多源 BFS——一次遍历就填完所有格子的最近距离，$O(m \cdot n)$。这种"反向 BFS"是求"到某集合最近距离"的通用技巧。

真正的 0-1 BFS 用武之地是"最少转弯"类问题：网格中移动代价为 0（直行）或 1（转弯），求最少转弯次数。直行不增加代价（权 0，push_front），转弯增加代价（权 1，push_back），一次 BFS 即得最优。

优先队列 BFS：Dijkstra 的雏形

当边权为任意非负值时，BFS 的"先发现即最短"不再成立——一条多边但权小的路径可能优于一条少边但权大的路径。这时需要按"当前已知最短距离"排序出队，这就是优先队列 BFS，即 Dijkstra 算法的雏形。

原理

用小顶堆（priority_queue + greater）按距离出队：每次取出当前距离最小的未确定节点，松弛其邻居。lazy deletion：节点可能因多次松弛而多次入队，出队时检查 if (d > dist[u]) continue 跳过过时记录。

#include <vector>
#include <queue>
#include <climits>

// 优先队列 BFS（Dijkstra 雏形）
// adj[u] = {(邻居 v, 权重 w)}，权值非负
int pqBFS(
    const std::vector<std::vector<std::pair<int,int>>>& adj,
    int start, int target) {
  int n = adj.size();
  std::vector<int> dist(n, INT_MAX);
  // 小顶堆：{距离, 节点}
  using P = std::pair<int,int>;
  std::priority_queue<P, std::vector<P>,
                      std::greater<P>> pq;
  dist[start] = 0;
  pq.push({0, start});
  while (!pq.empty()) {
    int d = pq.top().first;
    int u = pq.top().second;
    pq.pop();
    if (d > dist[u]) continue;        // lazy deletion
    if (u == target) return d;
    for (const auto& edge : adj[u]) {
      int v = edge.first;
      int w = edge.second;
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;        // 松弛
        pq.push({dist[v], v});
      }
    }
  }
  return dist[target] == INT_MAX ? -1
                                 : dist[target];
}

复杂度 $O((V+E)\log V)$。每个节点至多入队 $O(\text{度数})$ 次，每次堆操作 $O(\log V)$。

演化脉络

把这一节与前面串联起来，可以看到一条清晰的演化线：

$$\text{普通 BFS} \xrightarrow{\text{权值出现 0}} \text{0-1 BFS} \xrightarrow{\text{权值任意非负}} \text{优先队列 BFS} = \text{Dijkstra}$$

队列结构随权值复杂度递增：普通队列 → 双端队列 → 优先队列。0-1 BFS 是优先队列 BFS 在权值仅为 0/1 时的线性退化。详细的最短路算法（Dijkstra/SPFA/Floyd）留待最短路专题，本文只点明这条演化脉络。

值得提的还有搜索范式的对照：回溯算法 是隐式决策树上的 DFS，其 BFS 对应物是分支限界（优先队列 BFS + 界限剪枝）。这就形成了"回溯(DFS) → 分支限界(BFS) → 记忆化 → DP"的算法演进链——随着对状态空间的利用从"遍历"升级到"剪枝"再到"缓存重叠子问题"，搜索逐渐演化为动态规划。

双向 BFS

单向 BFS 在答案深度大时空间爆炸：分支因子 $b$、答案深度 $d$ 时搜索 $O(b^d)$ 个节点。双向 BFS 从起点和终点同时搜索，当两个搜索前沿相遇时即得最短路径，复杂度从 $O(b^d)$ 降到 $O(b^{d/2})$，指数级缩减。

正向: A → → → → ●               前沿向右推进
                ↓ 相遇点
反向:           ● ← ← ← ← B     前沿向左推进

总步数 = 正向步数 + 反向步数
搜索空间从 O(b^d) 降到 O(b^{d/2})

实现要点

• 交替扩展：每次选择较小的一侧前沿扩展（启发式平衡），避免一侧爆炸。
• 相遇判定：一边扩展出的节点出现在另一边的 visited 集合中，则相遇。
• 距离计算：dist_forward[u] + dist_backward[u] 即最短距离。

示例：单词接龙双向 BFS

#include <string>
#include <vector>
#include <unordered_set>

// 双向 BFS 加速单词接龙
int ladderLengthBiBFS(
    const std::string& beginWord,
    const std::string& endWord,
    std::vector<std::string>& wordList) {
  std::unordered_set<std::string> dict(
      wordList.begin(), wordList.end());
  if (!dict.count(endWord)) return 0;
  std::unordered_set<std::string> front{
      beginWord};
  std::unordered_set<std::string> back{
      endWord};
  dict.erase(beginWord);
  dict.erase(endWord);
  int steps = 1;
  while (!front.empty() && !back.empty()) {
    // 每次扩展较小的一侧
    if (front.size() > back.size())
      std::swap(front, back);
    std::unordered_set<std::string> next;
    for (const std::string& word : front) {
      std::string cur = word;
      for (int i = 0; i < (int)cur.size(); ++i) {
        char old = cur[i];
        for (char c = 'a'; c <= 'z'; ++c) {
          cur[i] = c;
          if (back.count(cur))
            return steps + 1;       // 相遇
          if (dict.count(cur)) {
            next.insert(cur);
            dict.erase(cur);        // 标记
          }
        }
        cur[i] = old;
      }
    }
    front = std::move(next);
    ++steps;
  }
  return 0;
}

关键差异。与单向 BFS 相比：(1) 用两个 unordered_set 代替队列，便于 $O(1)$ 判相遇；(2) 每轮只扩展较小的一侧，平衡两边的搜索树规模；(3) 相遇时 steps + 1——因为相遇点在两边各算了一步的交界。

适用前提：必须已知终点（求"起点到某特定终点的最短路"）。若求"到所有节点的最短路"，双向 BFS 无法使用，只能退回单向。

与 IDA* 的对称性。双向 BFS 是"空间换时间"（两边各存一层前沿，换取搜索空间减半），而 DFS 专篇 的迭代加深 IDA* 是"时间换空间"（反复重搜上层，换取空间降到 $O(d)$）。两者都是"单向搜索不够用"时的优化，读者可对照阅读。

A* 启发式搜索

A* 是优先队列 BFS 的启发式增强：在堆的排序键里加入一个"到终点的估计代价"，引导搜索向终点方向偏移，减少无用扩展。

估价函数

$$f(n) = g(n) + h(n)$$

其中 $g(n)$ 是起点到 $n$ 的已走代价，$h(n)$ 是 $n$ 到终点的估计代价。A* 按 $f$ 从小到大出队，优先扩展"总代价估计更小"的节点。

可采纳性与一致性

• 可采纳性（admissible）：$h$ 永不高估真实最短距离。这是 A* 给出最优解的充要条件。若 $h$ 可能高估，A* 可能跳过最优路径。
• 一致性（consistent）：$h(a) - h(b) \le \text{cost}(a, b)$。保证每个节点只扩展一次（无需 lazy deletion）。可采纳但不一致的 $h$ 仍正确，但节点可能重入队。

两个极端：$h = 0$ 时 A* 退化为 Dijkstra（无方向偏好）；$h$ 恰为真实距离时 A* 沿最优路径直奔终点（理想情况，几乎不扩展无用节点）。

常用启发式

• 网格最短路（四方向移动）：曼哈顿距离 $|x_1 - x_2| + |y_1 - y_2|$。
• 八方向移动：切比雪夫距离 $\max(|x_1-x_2|, |y_1-y_2|)$。
• 自由移动：欧几里得距离。

骨架

#include <vector>
#include <queue>
#include <cmath>
#include <climits>

// 网格 A*：h = 曼哈顿距离（四方向移动可采纳）
int astar(const std::vector<std::string>& maze,
          int sx, int sy, int tx, int ty) {
  int m = maze.size(), n = maze[0].size();
  const int dx[4] = {0, 0, 1, -1};
  const int dy[4] = {1, -1, 0, 0};
  auto h = [&](int x, int y) {
    return std::abs(x - tx) + std::abs(y - ty);
  };
  std::vector<std::vector<int>> g(m,
      std::vector<int>(n, INT_MAX));   // 已走代价
  // 小顶堆：{f, {x, y}}
  using P = std::pair<int, std::pair<int,int>>;
  std::priority_queue<P, std::vector<P>,
                      std::greater<P>> pq;
  g[sx][sy] = 0;
  pq.push({h(sx, sy), {sx, sy}});     // f = g + h
  while (!pq.empty()) {
    auto top = pq.top(); pq.pop();
    int x = top.second.first;
    int y = top.second.second;
    if (x == tx && y == ty)
      return g[x][y];                 // 到达终点
    for (int i = 0; i < 4; ++i) {
      int nx = x + dx[i], ny = y + dy[i];
      if (nx < 0 || nx >= m) continue;
      if (ny < 0 || ny >= n) continue;
      if (maze[nx][ny] == '#') continue;
      if (g[x][y] + 1 < g[nx][ny]) {
        g[nx][ny] = g[x][y] + 1;
        pq.push({g[nx][ny] + h(nx, ny),
                 {nx, ny}});
      }
    }
  }
  return -1;
}

与双向 BFS 的关系：两者都是"减少无用搜索"的优化，A* 用"估计"剪枝（不向远离终点的方向扩展），双向 BFS 用"两端夹击"剪枝（搜索空间减半）。两者可结合成双向 A*，在大规模寻路中效果显著。

A* 是游戏寻路（如 RTS、RPG 的自动寻路）的行业标准，地图导航（Google Maps、高德）也是 Dijkstra/A* 的工程化实现。当启发式设计得当，A* 能比 Dijkstra 节省几个数量级的搜索。

横向对比：DFS vs BFS

把 DFS 与 BFS 放进同一张表里系统对比，是本文的收束性板块。详细对比放在 BFS 篇，DFS 篇只放一句简短对照并指向本文。

维度	DFS（深度优先）	BFS（广度优先）
数据结构	栈（递归调用栈或显式栈）	队列（FIFO）
遍历形态	一条路走到底，无路才回退	逐层向外扩散
最短路保证	无（需枚举所有路径取最小）	无权图天然给出最短路
空间复杂度	$O(D)$，递归栈深度	$O(W)$，队列最大层宽
实现方式	常用递归，也可显式栈迭代	天然迭代（队列循环）
典型应用	连通性、环检测、拓扑排序、Tarjan、回溯枚举	最短步数、层序遍历、扩散模拟
是否需要回溯	连通性遍历不需要；枚举方案需要	不需要（无撤销动作）
树上语义	前/中/后序（纵向）	层序（横向）

几个易混点的澄清：

• 求最短/最少用 BFS，求可行/枚举用 DFS。这是最核心的分工口诀。BFS 的层序天然按距离排序，第一次到达即最优；DFS 找到的不一定最短，但找"是否存在可行解"时更省内存。
• 网格连通性（岛屿数量）用 DFS 洪泛，网格最短步数用 BFS。两者都是网格 + 方向数组，但目标不同：DFS 标记整块连通区域，BFS 求两点间最少步数。详见 DFS 专篇 的网格章节。
• 树的前中后序遍历用 DFS，层序遍历用 BFS。同一棵树，DFS 纵向切（根→左→右），BFS 横向切（一层一层）。
• 空间取舍：BFS 空间 $O(W)$（最大层宽），DFS 空间 $O(D)$（最大深度）。宽而浅的图用 DFS 省，深而窄的图用 BFS 省。链状图 DFS 会爆栈，宽扇出图 BFS 会爆队列。
• 共享机制：两者共享 visited 标记与方向数组模板，差别只在容器（栈 vs 队列）与推进顺序。访问标记的"入队即标记 / 入栈即标记"原理完全一致，详见 DFS 专篇 的访问标记章节。

交叉引用：DFS 详见 DFS 专篇，回溯（隐式决策树上的 DFS）见 回溯算法。三者构成搜索算法的完整版图。

实战场景：竞赛与工程应用

竞赛

BFS 是算法竞赛搜索题的主力：

• 网格最短路：迷宫、最短桥、最短路径变形，是 Div.2 C/D 题的常客。识别"四方向移动求最少步数"即可条件反射上 BFS。
• 状态空间 BFS：八数码、转盘锁、滑动谜题——把状态编码成字符串，unordered_set 记录访问，是面试与比赛的高频考点。
• 多源 BFS：腐烂橘子、火势蔓延、墙与门类题目，"所有源点同时入队"是标准套路。
• 0-1 BFS：看似需要 Dijkstra 实则线性的提速利器。识别"边权只有 0/1"（如最少转弯）是关键。
• 双向 BFS：单词接龙类题目中把 TLE 变 AC，竞赛中是"卡常"的最后一招。

竞赛手感上，BFS 的代码比 DFS 长（要维护队列、dist、方向数组），但逻辑更线性、不易在递归深度上踩坑。常见卡点在"入队时标记"与"dist 初始化为 -1"这两处。

工程

BFS 在工程中无处不在：

• 社交网络：k 度好友推荐、影响力传播分析，BFS 限定深度即可求"几度关系"。
• 网络爬虫：URL 边界队列本质是 BFS——按层抓取，控制深度避免无限递归。早期搜索引擎的爬虫就是 BFS 抓取。
• 路径规划：游戏寻路（A* 是行业标准）、地图导航（Dijkstra/A* 的工程化），地铁换乘推荐（最少换乘 = 无权图 BFS）。
• 广播与路由：网络包泛洪、消息扩散模拟、P2P 网络的节点发现。
• 扩散模拟：火灾蔓延、洪水扩散、疫情传播的元胞自动机，每一步都是一次"层"的扩展。
• 编译器：控制流图的可达性分析、死代码消除，本质是图遍历（DFS 或 BFS 均可，BFS 在求最短路径时更优）。
• 垃圾回收：可达性分析阶段从 GC Roots 出发标记存活对象，是图遍历的直接应用。

工程教训：BFS 的空间爆炸在生产中要设深度上限或节点数上限，否则大规模图会 OOM。比如爬虫不设深度会爬进递归页面陷阱，社交网络不设上限会遍历整个用户图。给 BFS 加上 max_depth 或 max_nodes 是常见的防御手段。

常见陷阱与边界条件

BFS 代码看似简单，但以下高频踩坑点每条都足以让一次提交从 AC 变 TLE/MLE：

1. 出队时才标记 visited：导致重复入队、队列膨胀、TLE/MLE。正确做法是入队时立即标记。这是 BFS 头号陷阱。

2. 起点忘记标记/入队：起点未标记会导致被邻居重新入队，dist 错乱。务必在 q.push(start) 的同时 visited[start] = true 或 dist[start] = 0。

3. dist 数组初始化错误：应用 -1 表示未访问（不能用 0，0 是起点的合法距离）；或用单独的 visited 数组区分。混用会导致"未访问"与"距离为 0"无法区分。

4. 方向数组写错：dx/dy 配对错位致方向错乱；四方向 vs 八方向混淆。常用 {0,0,1,-1}/{1,-1,0,0}，自检方法：打印移动后坐标验证。网格边界检查遗漏（< 0 或 >= n/m）会段错误。

5. 空间爆炸：大网格/大图上 BFS 队列可能存整层节点，需评估 $O(W)$ 空间上限。$10^5 \times 10^5$ 的网格 BFS 内存以 GB 计，必要时改 IDDFS 或 A*。

6. 多源 BFS 漏入队：所有源点必须一开始全部入队并标记，遗漏任一会得到错误的最远距离。腐烂橘子类题目中，漏掉一个初始腐烂橘子会导致"好橘子永远不被感染"的错误结论。

7. 状态编码冲突：状态空间 BFS 中，状态字符串/哈希若编码不唯一（如八数码的不同表示撞哈希），会漏访问。确保编码方案是双射。

8. 0-1 BFS 的松弛重入：与普通 BFS 不同，0-1 BFS 中节点可能因更优距离被重新入队，不能简单地"访问过就跳过"。必须用 dist[u] + w < dist[v] 的松弛条件判断。

9. ZigZag 方向翻转时机：奇偶层判断易差一（off-by-one），建议用 bool 标志每层翻转，而非用层号取模。层号从 0 还是从 1 开始要统一。

10. 整数溢出：dist 在大图上可能超过 int（如 $10^9$ 规模），状态哈希也可能溢出，必要时用 long long。

11. 起点即终点的边界：应直接返回 0，避免空队列入队逻辑出错。在迷宫 BFS 中，若 sx==tx && sy==ty，应在入队后第一次出队时就返回。

12. 网格四连通与八连通：题目要求对角线可达时方向数组要扩展到 8 方向，默认是 4 方向。读题时确认"相邻"的定义。

一个通用的自查清单：起点标记了吗？入队时标记还是出队时标记？dist 初始化为 -1 了吗？方向数组配对正确吗？越界检查在访问数组之前吗？多源是否全部入队？这六问能挡掉大部分 BFS bug。

小结

BFS 的三句话本质：

1. 它是 FIFO 队列驱动的层序搜索：先进先出保证"先发现的先扩展"，从而维持按距离分层推进。
2. 分层性质保证无权图最短路：第一次到达某点时的距离就是最短距离，这是 BFS 不可替代的核心价值。
3. 变体谱系统一在"队列结构"上：从树层序、网格、多源到 0-1 BFS、双向 BFS、A*，都是在 BFS 骨架上换数据结构（队列→deque→优先队列）或加启发式。

掌握 BFS 的路径：先把通用模板（图 + 网格）刻进肌肉记忆，再分场景（树层序、网格最短路、状态空间）练分层与多源，最后掌握 0-1 BFS 与双向 BFS 作为提速武器。

与 DFS 的分工口诀：求最短用 BFS、求可行/枚举用 DFS。BFS 空间 $O(W)$（最大层宽），DFS 空间 $O(D)$（最大深度）——宽而浅用 DFS，深而窄用 BFS。两者共享 visited 机制与方向数组模板，差别只在容器与推进顺序。DFS 详见 DFS 专篇，回溯（隐式决策树上的 DFS）见 回溯算法，三者构成搜索算法的完整版图。

演化脉络也值得铭记：普通 BFS → 0-1 BFS → 优先队列 BFS → Dijkstra，是一条"队列结构随权值复杂度递增"的演化线。A* 再在这条线上叠加启发式估计。理解了这条线，遇到任何"加权最短路"问题都能快速定位该用哪种工具。

最后，BFS 的核心不是"会写队列循环"——那只是几行模板——而是识别问题具有"无权最短路结构"的建模直觉。看到"最少操作次数"“最少步数”“最近可达”“层层扩散”，第一反应就该是 BFS。这种建模直觉比任何具体代码都更值得内化。