广度优先搜索

讲解

广度优先搜索（BFS）以起点为中心一圈一圈向外扩散：先访问距离 1 的所有节点，再距离 2 的……实现上就是一个队列：出队一个节点，把它的未访问邻居入队。因为按距离分层展开，BFS 有一个 DFS 不具备的皇牌性质：在无权图上，第一次到达某节点时走的步数就是最短路径。凡是无权最短路径问题（迷宫、转盘锁、单词接龙），BFS 是正解；DFS 找到的答案不保证最短。

二叉树层序遍历我们已经见过（size 快照分层的技巧同样来自 BFS），本章把视野放到网格和隐式图上。网格就是图：每个格子是节点，上下左右是边。岛屿数量的 BFS 解法：遇到陆地就把计数加一，然后从它出发 BFS，把整片岛「淹掉」（置 0），主循环继续扫——每个格子进出队列各一次，O(mn)。

隐式图更考验建模：打开转盘锁里，每个四位状态是节点，拨动一位数字产生 8 条边，目标是从 '0000' 到 target 的最短步数，deadends 是禁区。状态空间只有 10⁴，BFS 轻松覆盖。这类题的套路是：定义状态 → 写「状态生成函数」→ 套标准 BFS 模板（队列 + visited 集合 + 层计数）。visited 必须在入队时打标记（而不是出队时），否则同一节点会被重复入队，队列指数膨胀。

示例

网格 BFS（岛屿数量）+ 隐式图 BFS（打开转盘锁，输出最短步数）：

import assert from 'node:assert/strict';

function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== '1') continue;
      count++; // 发现新岛
      const queue = [[r, c]];
      grid[r][c] = '0'; // 淹掉，防止重复计数
      while (queue.length > 0) {
        const [cr, cc] = queue.shift();
        for (const [dr, dc] of dirs) {
          const nr = cr + dr;
          const nc = cc + dc;
          if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
            grid[nr][nc] = '0';
            queue.push([nr, nc]);
          }
        }
      }
    }
  }
  return count;
}

function openLock(deadends, target) {
  const dead = new Set(deadends);
  if (dead.has('0000')) return -1;
  if ('0000' === target) return 0;
  const visited = new Set(['0000']);
  let queue = ['0000'];
  let steps = 0;
  while (queue.length > 0) {
    steps++;
    const next = [];
    for (const cur of queue) {
      for (let i = 0; i < 4; i++) {
        for (const delta of [1, -1]) {
          const digit = (Number(cur[i]) + delta + 10) % 10; // 环形 0-9
          const nxt = cur.slice(0, i) + digit + cur.slice(i + 1);
          if (dead.has(nxt) || visited.has(nxt)) continue;
          if (nxt === target) return steps; // BFS 首达即最短
          visited.add(nxt); // 入队时标记
          next.push(nxt);
        }
      }
    }
    queue = next;
  }
  return -1;
}

const grid = [
  ['1', '1', '0', '0', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '1', '0', '0'],
  ['0', '0', '0', '1', '1'],
];
assert.strictEqual(numIslands(grid), 3);

assert.strictEqual(openLock(['0201', '0101', '0102', '1212', '2002'], '0202'), 6);
assert.strictEqual(openLock(['8888'], '0009'), 1);
assert.strictEqual(openLock(['0000'], '8888'), -1);

console.log('BFS 示例全部通过');

openLock 里用「每轮处理一整层」（next 数组收集下一层）而不是在循环外随便 steps++，保证了步数与层数严格对应——这和二叉树层序的 size 快照是同一个技巧。

常见坑

• visited 出队才标记：同一节点被多个邻居重复入队，队列爆炸；必须入队时标记。
• 在无权图上用 DFS 求最短路径：DFS 先到的路径不一定最短，答案错误且隐蔽；无权最短路 = BFS。
• 网格忘记边界检查：四方向扩散先判 nr/nc 在界内再访问 grid，顺序反了会读到 undefined 而不报错（JS 不抛异常，更难查）。
• 淹没标记时机晚：发现陆地时立刻置 0 再入队，否则相邻陆地会重复入队（逻辑仍对，但队列冗余）。
• 大网格上 queue.shift() 拖慢：shift 是 O(n)，数据大时用头指针（let head = 0; queue[head++]）代替，本章示例为可读性保留 shift。

小结

BFS = 队列逐层扩散，无权图最短路径的正解；网格即图、隐式图先建模状态与边；visited 入队时标记。下一章深入 DFS 在图上的应用：图的表示与拓扑排序。