BFS 与最短路径
BFS 算法框架
它就是层序遍历，多了一个 visited
二叉树的层序遍历已经把框架写过了： 队列、每轮记下当前层的节点数、弹一个推它的孩子。
搬到图上只需要加一件事：visited。树没有环，节点不会被重复访问；
图处处是环，不记就会绕回去（同网格 DFS那一条）。
function bfs(start, target, neighborsOf) {
const q = [start];
const visited = new Set([start]);
let step = 0;
let head = 0; // 下标当队头，别用 shift()
while (head < q.length) {
const sz = q.length - head; // 🚨 先存下来，同层序遍历
for (let i = 0; i < sz; i++) {
const cur = q[head++];
if (cur === target) return step; // ⭐ 第一次碰到就是最短，见下
for (const next of neighborsOf(cur)) {
if (visited.has(next)) continue;
visited.add(next); // 🚨 入队时就标记，不是出队时
q.push(next);
}
}
step++; // 一层走完，步数加一
}
return -1;
}⭐ 为什么第一次碰到就是最短
BFS 是一圈一圈往外扩的：先走完所有 1 步能到的，再走 2 步能到的。 所以当它第一次碰到目标时，不可能存在更短的路径 —— 更短意味着在更早的某一圈就该碰到，而那一圈已经完整走过了。
这条性质是 BFS 相对 DFS 的唯一优势，也是它存在的全部理由。 DFS 也能找到路径，但找到的是「碰巧先撞上的那条」，不是最短的。
⚠️ 前提是每条边的代价相同（都算 1 步）。边有不同权重时这条性质立刻失效， 那时要换成 Dijkstra。
📌 判据很好记：题目问「最少几步」「最短距离」而每步代价一样 → BFS。 问「路径存不存在」「有多少条路径」→ DFS 更省内存。
🚨 visited 必须在入队时标记，不是出队时
这是 BFS 最经典的错误，而且它不影响正确性、只影响性能，所以极难发现。
出队时才标记的话，同一个节点会被多个邻居先后推进队列，队列里躺着一堆重复项。 答案照样对（第一次弹出来的仍然是最短的那条），但队列会膨胀。
拿一个 12 节点的完全图遍历到底实测：
入队标记：入队 12 次，队列峰值 11
出队标记：入队 67 次，队列峰值 56 ← 5.6 倍 / 5.1 倍🚨 但「5.6 倍」是完全图给的错觉，网格上它是组合爆炸
同一段代码换成网格，遍历到底的入队次数：
入队标记 出队标记 膨胀
4×4 16 69 4.3×
6×6 36 923 25.6×
8×8 64 12,869 201.1×
10×10 100 184,755 1,847.5×
12×12 144 2,704,155 18,778.9×
14×14 196 40,116,599 204,676.5×
15×15 225 跑不完 —— 入队数超过 JS 数组长度上限，抛 RangeError⭐ 不是「乘个常数」，是每个节点被出队的次数等于起点到它的最短路径条数。
10×10 网格里最角上那个格子被出队 48620 次 —— 那正是 C(18,9)。
于是总入队次数有闭式解：
n×n 网格从角出发，总入队次数 = Σ C(r+c, r)
实测入队 Σ 最短路径条数 Σ C(r+c,r)
4×4 69 69 69
6×6 923 923 923
8×8 12,869 12,869 12,869
10×10 184,755 184,755 184,755
12×12 2,704,155 2,704,155 2,704,155 ← 三者逐位相同⚠️ 这个刻画有条件：只在二分图上成立（层内没有边）。 网格、树、转盘锁都是二分图；完全图不是 —— 它同层之间也连边， 所以 K12 上每个节点只被出队 1~11 次，看起来温和得多。 正文最早那个「5.6 倍」正是这么来的：拿唯一一个不适用的例子去量它。
📌 判据：要量一个「重复项会不会失控」的 bug，别用完全图。 完全图每层几乎就是全图，重复项没有繁殖的余地； 稀疏的层状图（网格、状态空间）才是它真正的舞台。
⚠️ 症状是「小数据全过、大数据超时或爆内存」，看起来像算法选错了， 实际只差这一行的位置。而答案从头到尾都是对的，所以对拍发现不了 —— 2042 组随机起终点上答案错 0 组。
⚠️ 另有一个变体值得单独说：如果你把入队处的标记删了，
却忘了把 visited 的初始值也一起改（仍写 new Set([start])），
那么起点一出队就被当成「访问过」直接 continue，BFS 一步都走不出去 ——
2042 组里错 2042 组，全部返回 -1。这一版不是慢，是彻底不工作。
双向 BFS
起点和终点都知道时，可以从两头同时扩，碰面就结束。
理论上省下的是数量级：单向 BFS 要扩到深度 d，节点数约 b^d（b 是分支数）；
双向只需要各扩 d/2，加起来 2·b^(d/2)。
🚨 但这个理论值在很多题上根本兑现不了，实测才发现。 三个图各跑一遍
（🚨 先说清口径：单向数「出队的节点数」，双向数「扩展过的节点数」，
即双向那个 for (const cur of a) 执行了多少次）：
单向出队 双向扩展 省下
4 叉 6 层的树（5461 个节点） 5,461 15 364×
60×60 网格，走对角 3,600 3,482 1.03×
转盘锁 0000 → 5555 10,000 7,491 1.33×⚠️ 这两列不是同一个口径，比值会被这件事撑大。 双向 BFS 除了「扩展」
还要把邻居塞进 visited，那些也是访问过的状态。换成两边都数
「碰过多少个状态」（单向的出队数 vs 双向的 visited.size）：
单向 双向visited 省下
4 叉 6 层的树 5,461 46 118.7× ← 不是 364×
60×60 网格 3,600 3,600 1.00× ← 一个都没省
转盘锁 0000 → 5555 10,000 10,000 1.00× ← 一个都没省⭐ 网格和锁那两行原来的 1.03× / 1.33× 全部来自口径差。 同口径下双向一个状态都没省 —— 它把整个空间都碰了一遍， 只是「扩展」的那一部分少些。原文写「少 1.0 倍」，字面意思正是「没少」。
⭐ 差别在于状态空间有没有边界：
- 树是指数扩张的，越走越宽，永远填不满 —— 少扩一半深度就是天壤之别
- 网格和转盘锁是有界的，一共就那么多状态。 单向 BFS 反正也要把它们基本走完，双向连常数都改不动
⚠️ 还有一件表里看不出来的事：那两行的单向格恰好等于状态空间总数。 3600 和 10000 就是 60×60 和 10⁴ —— 因为终点选的是离起点最远的那个 （对角 118 步、5555 需要 20 步，都是直径）。换个近一点的终点， 两者立刻都省下大半：
转盘锁，起点固定 0000 距离 单向出队 双向visited 省下
0000 → 5555 20 10,000 10,000 1.00×
0000 → 2222 8 2,308 457 5.05×
0000 → 0005 5 677 168 4.03×
0000 → 1111 4 161 51 3.16×📌 判据：「双向省多少」不是算法的性质，是「终点有多远」的性质。 拿直径当终点量出来的比值是这道题的下界，不是它的典型值。
👉 更准的判据：状态空间远大于「必须访问的部分」时，双向才划算。 BFS 无论如何都要填满整个空间的题（终点在直径上就是这种），双向 BFS 是白忙。
⚠️ 顺带说一句：「转盘锁用双向 BFS 优化」是流传很广的说法， 但最远那一档实测同口径下 1.00 倍 —— 一个状态都没省。 真要有收益，得是终点不太远的那些用例。
function bidirectionalBFS(start, target, neighborsOf) {
if (start === target) return 0;
let a = new Set([start]); // 从起点扩的边界
let b = new Set([target]); // 从终点扩的边界
const visited = new Set([start, target]);
let step = 0;
while (a.size > 0 && b.size > 0) {
// ⭐ 每轮都从**小的那一头**扩。两边规模常常差很多，
// 总是扩小的能显著减少总访问量 —— 这一行是双向 BFS 的关键优化，
// 不是可有可无的整理。
if (a.size > b.size) [a, b] = [b, a];
const next = new Set();
for (const cur of a) {
for (const n of neighborsOf(cur)) {
if (b.has(n)) return step + 1; // 撞上另一头了
if (visited.has(n)) continue;
visited.add(n);
next.add(n);
}
}
a = next;
step++;
}
return -1;
}⭐ 那行「总扩小的那一头」不是整理代码，是真优化。同一棵 4 叉 6 层的树上实测： 换边扩展 15 个节点，不换边 1365 个 —— 91 倍。 两头规模常常差很多（终点那边往往只有一条路上来），总扩小的那头能少走一大片。
⚠️ 这个倍数随树的深度一直往上涨，不是固定值：
4 叉 d 层 换边扩展 不换边扩展 倍数
4 层（341） 4 85 21.3×
5 层（1365） 8 341 42.6×
6 层（5461） 15 1,365 91.0×
7 层（21845） 31 5,461 176.2×⭐ 规律很干净：不换边就等于从起点单向扩到底（85/341/1365/5461 正是 上一层的节点总数），换边则只沿着终点那条细链上来。 所以这不是「优化了一个常数」，是把指数的底数换掉了 —— 数据越大差得越多，永远不要因为「小数据上差不多」就把这行删了。
⚠️ 双向 BFS 有个硬前提：必须事先知道终点。 「找出所有距离起点 3 步的节点」这种题用不上它。
⚠️ 另外它用 Set 而不是队列 —— 因为要频繁做「另一头有没有这个节点」的查询。
用数组的话每次查询是 O(n)，优化直接白做。
典型题的共同点：状态就是节点
网格题里「节点」是显然的（一个格子）。但 BFS 真正的威力在于 把抽象状态当成节点：
- 打开转盘锁 —— 节点是四位数字的当前状态（
"0000"）， 邻居是拨动任意一位得到的 8 种状态 - 最小基因变化 —— 节点是基因串，邻居是改一个字符后仍在库里的串
- 单词接龙 —— 节点是单词，邻居是差一个字母的词
⭐ 这三道题的图不是给你的，是你自己定义出来的。 一旦想清楚「什么是节点、什么是邻居」，剩下的就是套上面那个框架。
📌 卡住的时候先问这两个问题，而不是先想怎么写代码。
复杂度
时间 O(V + E)，每个节点进出队列一次、每条边看一次。
空间 O(V)，队列最坏装下一整层，visited 装下所有节点。
⚠️ BFS 的空间常常比 DFS 大得多：DFS 的栈深是路径长度， BFS 的队列宽是一层的节点数。宽而浅的图上，BFS 可能爆内存而 DFS 不会。 「用 BFS 还是 DFS」有时候是被内存逼出来的，不是被题意。
⚠️ 但「BFS 更费内存」只在树那一类图上成立，网格上正好相反。 实测四个图：
BFS队列峰值 DFS栈深(下界) 节点数
4 叉 6 层树 4,096 ≥6 5,461 ← BFS 贵 680 倍
60×60 网格 60 ≥3,599 3,600 ← DFS 贵 60 倍
转盘锁 1,342 ≥9,999 10,000 ← DFS 贵 7 倍
K200 完全图 199 ≥199 200 ← 打平⭐ 网格上 BFS 的队列峰值只有 60（那是对角线的长度）， 而 DFS 能沿着一条蛇形路径走遍全部 3599 个格子 —— 递归深度直接爆栈。 📌 判据：分支多而浅 → BFS 费内存；分支少而深 → DFS 费内存。 网格四邻里有两个方向是「回头」，真正的分支只有 2，属于后者。
练习
勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。
- 102. 二叉树的层序遍历中等BFS 的原型
- 752. 打开转盘锁中等抽象状态当节点；双向 BFS 在 0000→5555 上同口径一个状态都没省
- 127. 单词接龙困难同上，邻居要自己定义
- 433. 最小基因变化中等与打开转盘锁同构
- 994. 腐烂的橘子中等多源 BFS：起点不止一个
- 542. 01 矩阵中等多源 BFS 求距离
⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。