图系列第 4 篇：广度优先搜索 BFS

嘿，朋友，欢迎回到图系列。这是第 4 篇，我们要正式学习图论与算法题里最重要的遍历算法之一——广度优先搜索，英文叫 Breadth-First Search，江湖人称 BFS。

在出发之前，先快速回顾前三篇我们都攒下了什么装备。第 1 篇我们建立了图的基本概念：图由顶点和边组成，边可以有方向、可以有权重，我们还认识了度、路径、环、连通这些基础词汇；第 2 篇我们把注意力放在连通性上，讨论了连通分量、有向图的强连通，以及如何判断”两个点是否在同一个连通块里”；第 3 篇我们解决了”图在计算机里到底怎么存”的问题，介绍了邻接矩阵和邻接表两种存储方式，并对比了它们的时空代价，最后的结论是：稀疏图用邻接表，稠密图才考虑邻接矩阵。今天这篇，我们要在这两块地基上盖第一栋大楼：给定一张图和起点，如何把整张图系统地”走遍”？而且不只是走遍——我们还要让访问顺序具备一个漂亮的规律，好用它去解决最短步数这类问题。

如果你读过树系列的第 6 篇，你一定会觉得今天的内容似曾相识：那一篇我们讲了二叉树的层序遍历，用队列把树一层一层扫过去。没错，广度优先搜索就是层序遍历在图上的一般化。两者用同一个核心工具——队列，遵循同一条铁律——先来先服务。区别只在于：树天然没有环，每个节点只有一个父亲，从根出发一路往下不会绕回自己；而图可以有环，同一个顶点可能被好几条路径同时到达，如果我们不加以标记，BFS 就会原地转圈，永远停不下来。今天的重头戏之一，就是把这个”标记”（visited）彻底讲透。

本篇的路线图如下：先建立”水波式扩散”的直观感受，说清楚 BFS 和树的层序遍历是什么关系；然后给出算法步骤和伪代码，把”队列 + visited”这对搭档拆开看；接着拿一张具体的无向图从头到尾手算一遍，每一步都把队列内容画出来；再深入讨论 visited 为什么必不可少、什么时候可以省略；随后给出 JavaScript / TypeScript 的邻接表实现并逐行解释；然后进入本篇最迷人的部分——BFS 为什么能找到无权图的最短路径，以及如何用 dist 数组和前驱数组把路径还原出来；之后介绍四个经典应用：迷宫最短步数、多源 BFS、单词接龙、状态空间搜索；最后预告第 5 篇的深度优先搜索（DFS），并附上一张速查表和一组自测题。

好，把水杯放好，我们从”水波”开始。

1 直观：从起点像水波一样扩散

1.1 往池塘里扔一颗石子

想象你往平静的池塘里扔了一颗石子。水面会泛起一圈一圈的涟漪：第一圈先出现，然后第二圈、第三圈……每一圈都比上一圈大，而且同一圈上的水波几乎同时到达。BFS 就是这样走的：从起点出发，先访问所有”距离起点 1 条边”的顶点，再访问所有”距离起点 2 条边”的顶点，以此类推。它不急着往深处钻，而是先把手边这一圈全部看完，才往外走下一圈。

下面这张图把”水波”画成了分层的样子。起点 A 在最中心，距离它 1 条边的是 B、C、D，距离 2 条边的是 E、F，距离 3 条边的是 G、H：

graph LR
    subgraph L0["距离 0（起点）"]
        S["A"]
    end
    subgraph L1["距离 1"]
        B["B"]
        C["C"]
        D["D"]
    end
    subgraph L2["距离 2"]
        E["E"]
        F["F"]
    end
    subgraph L3["距离 3"]
        G["G"]
        H["H"]
    end
    S --- B
    S --- C
    S --- D
    B --- E
    C --- F
    D --- F
    E --- G
    F --- H

请盯住这张图十秒钟，记住三个事实。第一，访问是一圈一圈进行的：A 是第 0 圈，B、C、D 是第 1 圈，E、F 是第 2 圈，G、H 是第 3 圈。第二，同一圈内部的先后顺序取决于入队顺序：谁先被发现、谁先排队，谁就先被访问。第三，每一圈都比上一圈”远一条边”：B 到 A 只有 1 条边，而 G 到 A 要走 B → E → G 或 F → G，一共 3 条边。这三点合起来，就是 BFS 的全部灵魂。

“水波”这个比喻还有一层意思：如果我们问”从 A 出发，最快几条边能到 G”，BFS 会给出答案 3。因为水波是同步外扩的，当第 3 圈的水波第一次碰到 G 时，已经不存在”更近的路”了——任何更近的路都会在第 2 圈或更早被水波扫到。这个朴素的想法，后面会严格证明，它就是 BFS 能解无权最短路的根本原因。

顺便统一一下术语：BFS 有时候叫广度优先遍历，有时候叫广度优先搜索。两者是同一个算法，侧重点略有不同——“遍历”强调把能到的顶点全部走一遍，“搜索”强调带着目标去找（常常提前终止）。我们后面两种说法都会用，但请记住它们背后的同一套流程。

1.2 和树的层序遍历是什么关系

树系列的读者对”层序遍历”一定不陌生：从根开始，先访问第 0 层，再访问第 1 层，再访问第 2 层……每一层内部从左到右。二叉树层序遍历的顺序是 A、B、C、D、E、F、G，这和我们刚才的水波扩散简直是一回事。事实上，层序遍历就是 BFS 在”树”这种特殊图上的名字。

为什么这么说？因为树本身就是一张图：节点就是顶点，父子连线就是边，根就是起点。对树做 BFS，从根出发一层一层扫，扫出来的顺序正是层序遍历。反过来，对任意图做 BFS，如果无视环的存在，它就像把图”当成一棵树”来一层一层铺开。两者共用的机制完全一样：一个队列，从起点开始，每访问一个节点，就把它的”孩子们”（树里是左右孩子，图里是邻居）加入队尾。

用一张并排图来对比最清楚。左边是一棵二叉树，右边是一张带环的无向图：

graph LR
    subgraph T["树：没有环，每个节点只有一个父亲"]
        R["R"]
        TL["L"]
        TR["R2"]
        TLL["LL"]
        TLR["LR"]
        R --- TL
        R --- TR
        TL --- TLL
        TL --- TLR
    end
    subgraph G["图：可能有环，一个顶点可以被多条路径到达"]
        P["P"]
        Q["Q"]
        W["W"]
        P --- Q
        Q --- W
        W --- P
    end

看右边的三角形：P 连着 Q，Q 连着 W，W 又连回 P。如果从 P 出发做 BFS，P 会把 Q 加入队列，Q 会把 W 加入队列，轮到 W 时，W 看到邻居 P 已经被访问过了——如果没做记录，W 会把 P 再次入队，然后 P 又把 Q 入队……水波会变成原地打转的漩涡。树的左边就不会有这个问题：每个节点只有一个父亲，从根出发不存在任何回路。

1.3 图与树的本质区别：必须记住”谁来过”

所以图上的 BFS 与树上的层序遍历，唯一的本质区别就是：图需要一张”已经来过”的名单。我们把这张名单叫作 visited（访问标记），实现上可以是一个布尔数组、一个 Set，或者一张”距离表”（用 -1 表示没来过）。每当我们把一个顶点加入队列，就立刻在名单上登记；以后任何路径再碰到它，直接无视。

这也解释了树系列第 6 篇里那个轻描淡写的小结论：二叉树层序遍历不需要 visited，因为树是”无环 + 单父亲”结构；而图系列从这一篇开始，visited 几乎永远在场。记住这句话：在树上，访问顺序由结构天然保证；在图上，访问顺序必须靠队列和 visited 联合保证。

1.4 把图展开成一棵虚拟的树

我们刚才反复提到”层""圈""距离”，这些词其实都指向同一个更本质的图景：BFS 的过程，就是把一张可能带环的图，展开成一棵以起点为根的”虚拟树”。 树的每一层对应一个距离，树中每个顶点都记录着”我是从谁那里第一次被发现的”。

为了看清这一点，我们把第 1.1 节那张分层图重新组织一下：每个顶点只保留”第一次发现它的那条边”，其余边暂时藏起来。你会发现，原来的图立刻变成了一棵规规矩矩的树——没有环、没有交叉，每个顶点只有一个父亲。这棵树就叫 BFS 树（BFS Tree），第 3 章我们会亲手从一张九顶点的图上把它”长”出来。先看它长什么样：

graph TD
    A["A（根）"] --- B["B"]
    A --- C["C"]
    A --- D["D"]
    B --- E["E"]
    C --- F["F"]
    E --- G["G"]
    F --- H["H"]
    H --- I["I"]

请对比第 1.1 节的图：原来的 D—F 和 G—H 这两条边，在展开后的树里不见了，因为 F 第一次被发现时，是被 C 发现的（D 慢了一步）；H 第一次被发现时，是被 F 发现的（G 慢了一步）。图里允许”一个顶点有好几个邻居都认识它”，但 BFS 只认”谁第一个发现它”。 这就是为什么 BFS 树里的每个顶点只有一个父亲——第一个发现它的人。

这棵虚拟树有两个巨大的好处。第一，树没有环，所以我们可以放心地在树上做各种推导，比如”树中从根到某个顶点的路径长度，就是这个顶点到起点的距离”。第二，树的层次结构给了我们”层”这个免费坐标：同一层的顶点距离相同，不同层严格按层排序，谁先谁后一目了然。后面讲最短路径时，这棵虚拟树会反复出场，请务必记住它的模样——它是理解 BFS 一切性质的钥匙。

1.5 有向图与无向图：BFS 都管用

前面所有的例子都是无向图，有同学可能会担心：BFS 是不是只适用于无向图？当然不是。在有向图里做 BFS，唯一的变化是”邻居”的定义：u 的邻居是”从 u 出发、沿箭头能直接到达的那些顶点”，也就是 u 的出边终点。入边不算，因为不能逆着箭头走。

举个例子，如果有一条边 A → B，从 A 出发做 BFS 能到达 B；但从 B 出发做 BFS 到不了 A。这个不对称性正是有向图的灵魂，BFS 只是忠实地遵循它。如果反过来，我们需要”能到达 u 的所有顶点”，可以把所有边反向，再做一次 BFS；这种”反向图”技巧在拓扑排序和强连通分量问题里会反复出现。

无向图里的一条边 A—B，等价于两条有向边 A → B 和 B → A。所以你也可以把无向图”翻译”成有向图，用同一套 BFS 处理。这解释了为什么 BFS 的代码不需要区分图的方向：方向已经被邻接表吸收掉了——无向图的邻接表里，A 的邻居表里有 B，B 的邻居表里也有 A；有向图则只记录出边邻居。剩下的算法逻辑一字不改。

1.6 动手体验

概念先讲到这里。动手是最快的理解方式，如果你还没有玩过图算法可视化实验室，强烈建议现在打开下面的实验室，自己建一张图，选一个起点，点一下”BFS”，亲眼看看水波是怎么一圈一圈扩散的。看着动画再回来读后面的手算走查，你会觉得每一步都像老朋友重逢：

好，直观有了，现在我们把”水波”翻译成严格的算法步骤。

2 算法步骤：队列 + visited

2.1 队列：为什么是”先来先服务”

BFS 的英文名字里有个”先”字（Breadth-First，宽度优先），它的实现里最重要的数据结构就是队列（Queue）。队列是”先进先出”（FIFO，First In First Out）的：先入队的人站在队首，先被服务；后入队的人排到队尾，耐心等待。这和我们排队买奶茶一模一样——先来的先拿，后来的后拿，插队是不允许的。

为什么 FIFO 恰好能实现”一圈一圈扩散”？我们可以这样想：起点 A 先入队，它是唯一的第 0 圈成员。A 出队时，把第 1 圈的 B、C、D 依次放入队尾；此时队列里只有 B、C、D，队首是 B。B 出队时，把第 2 圈的 E 放入队尾，队列变成 C、D、E。C 出队，放入 F，队列变成 D、E、F。注意，无论第 2 圈的新成员如何加入，队首永远都是第 1 圈的人，直到第 1 圈的 D 也出队，第 2 圈的人才轮到。也就是说，队列天然把”更近一圈”的顶点排在前面，因为他们是更早被发现的。水波之所以同步，不是因为有什么魔法，而是因为队列让”先发现的人先被处理”。

2.2 完整步骤

BFS 的标准流程可以压缩成四句话：

1. 初始化：把起点放入队列，并标记为已访问。
2. 出队：从队首取出一个顶点 u，对它进行”访问”（打印、计数、记录距离、检查是否为目标……随需求而定）。
3. 扩展：依次查看 u 的每一个邻居 v；如果 v 还没有被访问过，就把它标记为已访问，并放入队尾。
4. 循环：重复第 2、3 步，直到队列为空。

第 4 步的”直到队列为空”保证了算法一定终止：每个顶点最多入队一次，队列只会越来越短。这也是 visited 的第一份功劳——它不光是防止死循环，还保证了每个顶点最多被处理一次，让复杂度可控。

下面这张流程图把这四句话画了出来，你可以把它当作 BFS 的”说明书”贴在脑门上：

graph TD
    Init["初始化：visited 记录起点，起点入队"] --> Check{"队列为空？"}
    Check -- "否" --> Pop["取出队首 u"]
    Pop --> Visit["访问 u（打印 / 记录距离 / 检查目标）"]
    Visit --> Scan["遍历 u 的所有邻居 v"]
    Scan --> Seen{"v 在 visited 中？"}
    Seen -- "否" --> Mark["标记 v 并放入队尾"]
    Mark --> Scan
    Seen -- "是" --> Skip["忽略 v，继续下一个邻居"]
    Skip --> Scan
    Scan --> Check
    Check -- "是" --> Done["结束"]

2.3 伪代码

把上面的流程写成伪代码，长这样：

BFS(图 G, 起点 s):
    queue ← 新建空队列
    visited ← 新建空集合
    visited.add(s)
    queue.push(s)

    当 queue 不为空:
        u ← queue.pop()          // 队首出队
        访问 u                    // 打印、统计、记录 dist 等
        对于 u 的每个邻居 v:
            如果 v 不在 visited 中:
                visited.add(v)   // 先登记，再入队
                queue.push(v)

这段伪代码只有五行”干货”：一个队列、一个 visited、一个出队循环、一个邻居循环、一个”没来过才入队”的判断。后面所有的代码实现，本质上都是这五行的换皮。

2.4 一个容易被忽视的细节：入队时就要标记

细心的读者会注意到，我在伪代码里写的顺序是”先 visited.add(v)，再 queue.push(v)“，而不是”出队时才标记”。这是 BFS 最常见的坑，值得单独拿出来讲。

假设我们不立即标记，而是等 v 真正出队时才标记。考虑无向图中 A—B 这条边：A 出队时发现 B 没来过，把 B 入队；紧接着处理 A 的另一个邻居时当然没影响，但等队列里出现第二个指向 B 的顶点 X 时，X 也会发现”B 还没标记”，于是又把 B 入队。结果队列里可能出现两份、三份 B。虽然最终仍然会访问 B，但重复入队会带来两个坏处：一是队列里出现冗余，浪费空间和时间；二是如果我们在出队时做”第一次出队才记录距离”之类的操作，逻辑会变得混乱，容易写错。

正确做法是在入队的那一刻就标记。这样一来，B 只有第一次被发现时会入队，后续任何路径再碰到 B，都会因为 visited 里已经有它而直接跳过。这个细节可以用一句话记住：“先登记，再排队”，而不是”排队了回头再登记”。

2.5 六个常见错误清单

写 BFS 出 bug 的位置高度集中，提前把这些坑列出来，能帮你省下大量调试时间。

1. 忘记初始化 visited：起点没标记就入队，第一轮循环里起点可能被自己的邻居再次发现，队列里出现两份起点。
2. 出队时才标记：这就是 2.4 节说的”先排队、回头再登记”，队列会出现重复顶点，最坏情况下程序指数级变慢甚至死循环。
3. 邻居循环里漏掉 visited 判断：有人记得出队后判断 u 是否已访问，却忘了对每个邻居 v 单独判断”是否已访问”，结果把所有邻居全部入队，回到错误 2。
4. 用 pop() 取元素：pop() 从尾部取元素，得到的是栈（后进先出），BFS 立刻退化成”深度优先”，层次性质全部丢失。JavaScript 的数组同时有 push/pop/shift/unshift，写 BFS 时一定要用 shift() 取队首（或者用头指针实现真正的队列）。
5. 无向图漏掉”回头边”：A—B 这条边，A 出队时 B 入队；B 出队时看到邻居 A，如果 A 不在 visited 里，就会把 A 再入队。两个顶点互相入队，永远循环。visited 判断必须覆盖每一个邻居。
6. 网格 BFS 忘记边界检查：上下左右四个方向很容易越界，必须先判断新坐标在范围内、再判断是不是墙、再判断是否访问过，顺序不能乱。

把这份清单贴在代码旁边，写完 BFS 后逐条自查一遍，绝大多数 bug 都能当场消灭。接下来看一个正常流程里队列长什么样。

2.6 队列变化长什么样

在进入手算走查之前，先用一个小例子感受队列的变化。假设起点是 A，A 的邻居是 B、C、D，B 的邻居是 A、E，C 的邻居是 A、E、F：

graph LR
    subgraph S1["第 1 步：A 入队"]
        Q1["队列：[A]"]
    end
    subgraph S2["第 2 步：A 出队，B、C、D 入队"]
        Q2["队列：[B, C, D]"]
    end
    subgraph S3["第 3 步：B 出队，E 入队"]
        Q3["队列：[C, D, E]"]
    end
    subgraph S4["第 4 步：C 出队，F 入队"]
        Q4["队列：[D, E, F]"]
    end

注意第 3 步和第 4 步：E、F 都是第 2 圈的顶点，但他们只能排在 D（第 1 圈的最后一人）后面。这就是队列的纪律：后来的必须排在先来的后面，无论你离起点多远。 而”先来的”恰好总是更靠近起点，所以队列从头到尾都是”距离非降”的——这个性质我们到第 6 章还会用。

理论部分到这里就齐了。接下来，我们挑一张具体的图，从指定起点开始，一步步把它走完。

2.7 队列的工程实现

伪代码里写 queue.push 和 queue.pop，看起来轻描淡写，但真正写代码时，队列用什么实现是有讲究的。我们分三层说。

第一层：语言自带队列。 Python 的 collections.deque、Java 的 ArrayDeque、C++ 的 std::queue 都是双端队列，头尾操作都是 O(1)，直接用最省心。JavaScript 的数组比较特殊：push 和 pop 是 O(1)，但 shift（取队首并移除）在引擎里需要把剩余元素整体前移，最坏情况是 O(n)。小图无所谓，大图里用数组 shift 的 BFS，复杂度会从 O(V+E) 悄悄退化成 O(V²)。

第二层：头指针模拟。 在 JS/TS 里不想引入额外依赖，可以用一个普通数组加一个头指针：只 push，不 shift；出队时读 queue[head]，然后 head 加 1。数组里的旧元素虽然还在，但永远不会再被读到，等 head 超过数组一半时再整体截断一次。这个技巧让”出队”变成 O(1)，代码只多两行，是竞赛党的常用手段。

第三层：什么时候不必较真。 顶点数只有几千时，shift 的开销完全可忽略；算法题追求的是思路正确，工程题追求的是常数小。我的建议是：先写清楚正确的版本，再根据数据规模决定是否优化队列实现——不要为了一个 shift 的常数，把代码的可读性牺牲掉。

最后提醒一句：队列像”待办清单”，栈像”一摞盘子”，两者是完全不同的性格。栈是”后进先出”，适合回溯场景，那是 DFS 的家；队列是”先进先出”，适合扩散场景，这是 BFS 的家。选错数据结构，算法的性格就变了。

2.8 三种终止方式

BFS 的 while 条件几乎都是”队列不为空”，但”什么时候停止处理”其实有三种常见变体，对应三种不同的题目。

第一种：全部遍历。 队列清空才停，适合”求整个连通分量的访问顺序""数连通块""判断两个顶点是否可达”这类要完整结果的题目。

第二种：提前终止。 出队时检查目标，一旦命中立刻返回，适合”求最短距离、最少步数”的题目。因为 BFS 的性质保证第一次碰到目标就是最优，多跑一层都是浪费。

第三种：限层终止。 额外记录当前层号，超过上限就停止，适合”只关心 k 层以内”的问题，比如社交网络的三度人脉、传染病几轮传播后的范围、消息几跳之内能覆盖哪些节点。

三种变体的代码差别极小，但语义差别很大。拿到题目先问自己一句话：我要的是”全图结果”还是”最早命中”还是”限层覆盖”？ 把终止条件想清楚再动手，能避免一半以上的返工。

2.9 趁热打铁：一个 30 秒小练习

在进入手算走查之前，先用一个极小的例子检验你是否真的理解了流程。图有三条边：A—B、B—C、C—A，外加一条尾巴 C—D。从 A 出发，邻居按字母序扫描，BFS 的访问顺序是什么？队列最多同时有几个顶点？

答案是：访问顺序 A、B、C、D；队列变化为 [A] → [B, C] → [C] → [D] → []，最多同时有 2 个顶点。逐轮核对：A 出队，B、C 入队；B 出队，邻居 A、C 都已访问，无新人；C 出队，邻居 A、B、D 中只有 D 未访问，D 入队；D 出队，结束。如果你把 D 算到了 B 的下面，多半是把图看岔了——B 并不直接连 D。这个小练习虽然只有四个顶点，却同时覆盖了”入队时标记""回头边跳过""新层追加在队尾”三个关键动作，值得用笔在纸上完整写一遍。

3 手算走查：从 A 出发把整张图走一遍

3.1 走查用的图

为了把每一步都看得很清楚，我们用一张九个顶点、十条边的无向图。顶点是 A 到 I，边如下：A—B、A—C、A—D、B—E、C—E、C—F、D—F、E—G、F—H、G—H、H—I。等下，我数了一下，这是十一条边，让我们把图画出来，一边看一边数：

graph TD
    A((A)) --- B((B))
    A --- C((C))
    A --- D((D))
    B --- E((E))
    C --- E
    C --- F((F))
    D --- F
    E --- G((G))
    F --- H((H))
    G --- H
    H --- I((I))

对，是十一条边。你可以先用眼睛回答三个问题：这张图连通吗？A 到 I 有几条简单路径？A 的度是多少？答案是：连通（从任意顶点都能走到任意其他顶点）；A 到 I 有多条路径，比如 A→C→F→H→I 和 A→B→E→G→H→I；A 的度是 3，邻居是 B、C、D。读图的三个标准动作是数顶点、数边、找环：这里有 9 个顶点、11 条边，环有好几个（A—B—E—C—A 就是一个三角形环）。这张图没有孤立点，所以从任意起点做一次 BFS 都能覆盖全部九个顶点；如果图不连通，就需要每个连通分量各做一次 BFS，第 6.7 节会回来说这个事。

在走查之前，还需要约法三章，否则”先访问谁”会有歧义。第一，邻居的遍历顺序：我们约定按照字母表顺序扫描邻居（A 的邻居按 B、C、D 的顺序，C 的邻居按 A、E、F 的顺序，以此类推）。这个约定不影响算法本质，只影响同一层内部的先后。第二，访问的含义：访问顶点时，给它盖一个访问序号章，从 1 开始递增。第三，记录方式：visited 集合用”已访问”三个字标注，队列用方括号表示，队首在左边。

3.2 一步一步走

第 0 步（初始化）：起点 A 入队，visited = {A}，队列 = [A]。

第 1 步：队首 A 出队，访问 A，序号 1。A 的邻居按字母顺序是 B、C、D，三个都还没访问，于是依次标记并入队。访问顺序：A；队列 = [B, C, D]；visited = {A, B, C, D}。

第 2 步：队首 B 出队，访问 B，序号 2。B 的邻居是 A 和 E；A 已在 visited 中，跳过；E 没来过，标记并入队。访问顺序：A, B；队列 = [C, D, E]；visited 增加 E。

第 3 步：队首 C 出队，访问 C，序号 3。C 的邻居是 A、E、F；A 和 E 都已访问，跳过；F 没来过，标记并入队。访问顺序：A, B, C；队列 = [D, E, F]。

第 4 步：队首 D 出队，访问 D，序号 4。D 的邻居是 A 和 F，都已访问，全部跳过。访问顺序：A, B, C, D；队列 = [E, F]。

第 5 步：队首 E 出队，访问 E，序号 5。E 的邻居是 B、C、G；B、C 已访问，跳过；G 没来过，标记并入队。访问顺序：A, B, C, D, E；队列 = [F, G]。

第 6 步：队首 F 出队，访问 F，序号 6。F 的邻居是 C、D、H；C、D 已访问，跳过；H 没来过，标记并入队。访问顺序：A, B, C, D, E, F；队列 = [G, H]。

第 7 步：队首 G 出队，访问 G，序号 7。G 的邻居是 E 和 H；E 已访问，H 也已在 visited 中（第 6 步标记的），全部跳过。访问顺序：A, B, C, D, E, F, G；队列 = [H]。

第 8 步：队首 H 出队，访问 H，序号 8。H 的邻居是 F、G、I；F、G 已访问，跳过；I 没来过，标记并入队。访问顺序：A, B, C, D, E, F, G, H；队列 = [I]。

第 9 步：队首 I 出队，访问 I，序号 9。I 的邻居只有 H，已访问，跳过。访问顺序：A, B, C, D, E, F, G, H, I；队列 = []。

第 10 步：队列为空，算法结束。九个顶点全部被访问，每个恰好一次。

3.3 每一步的队列快照

把上面的过程整理成一张表，每一行的队列都是”该步出队并访问之后”的状态：

步骤	出队访问	访问序号	出队后的队列	本次新标记
0（初始化）	—	—	[A]	A
1	A	1	[B, C, D]	B、C、D
2	B	2	[C, D, E]	E
3	C	3	[D, E, F]	F
4	D	4	[E, F]	无
5	E	5	[F, G]	G
6	F	6	[G, H]	H
7	G	7	[H]	无
8	H	8	[I]	I
9	I	9	[]	无

请重点观察队列长度的变化：0→1→3→3→3→2→2→2→1→1→0，先涨后落，像一条波浪。这正是 BFS 的典型”呼吸节奏”：每一层入队时队列变长，这一层全部处理完时队列又变短。还可以观察一个规律：序号 1 的 A 在队首时，队列里全是一圈内的顶点；序号 4 的 D 出队时，第 2 圈的 E、F 已经排队，但第 1 圈还没走完。 任何时候，队列里的顶点距离起点的”圈数”最多相差 1。

为了更直观，我把三个关键时刻的队列画成图。第一个是第 1 步之后，三个第 1 圈的顶点排队：

graph LR
    Head1["队首"] --- Q1["B"] --- Q2["C"] --- Q3["D"]

第二个是第 3 步之后，第 1 圈只剩 D，第 2 圈的 E 已经排在 D 后面：

graph LR
    Head2["队首"] --- Q4["D"] --- Q5["E"] --- Q6["F"]

第三个是第 5 步之后，第 1 圈全部清空，队列里全是第 2、3 圈的顶点：

graph LR
    Head3["队首"] --- Q7["F"] --- Q8["G"]

这三张图连起来看，就是 BFS 的”换层”过程：第 1 圈的人排在最前面，一边出队一边把第 2 圈的人追加到队尾；当第 1 圈最后一人 D 出队时，队列的”头”变成了第 2 圈的 E、F，第 3 圈的人则排在他们后面。层与层之间无缝衔接，谁也不会插队。

3.4 走查结果：分层访问树

最终访问顺序是 A(1)、B(2)、C(3)、D(4)、E(5)、F(6)、G(7)、H(8)、I(9)。如果只看”每个顶点是被谁第一次发现并入队的”，我们就得到一棵以 A 为根的树——这棵树叫 BFS 树（BFS Tree） 或广度优先生成树：

graph TD
    A["A（序号 1）"] --- B["B（序号 2）"]
    A --- C["C（序号 3）"]
    A --- D["D（序号 4）"]
    B --- E["E（序号 5）"]
    C --- F["F（序号 6）"]
    E --- G["G（序号 7）"]
    F --- H["H（序号 8）"]
    H --- I["I（序号 9）"]

在这棵树上，每个非根顶点只有一条”被发现边”：B 是被 A 发现的，E 是被 B 发现的，F 是被 C 发现的，H 是被 F 发现的，I 是被 H 发现的。原图里的 G—H、D—F 这些边没有成为”发现边”，因为两端在被发现之前已经由别的路径打通过——它们被称为非树边。注意一个有意思的细节：G 是被 E 发现的，而不是被 H 发现的，因为 E 在第 5 步就先出队了；如果邻居顺序不同，G 也可能被 H 发现，但它所在的层不会变，它离 A 的距离永远是 3 条边。

BFS 树的价值非常大：树中从根到任意顶点的路径，就是图中从起点到该顶点的最短路径之一。比如树中 A→C→F→H→I 一共 4 条边，原图里任何 A 到 I 的路径都不可能少于 4 条边。为什么？这就是第 6 章要证明的核心定理。先不剧透，我们先把 visited 这个”配角”彻底研究明白，因为它是整个正确性的地基。

3.5 换个起点，再走一遍

只看一个起点容易产生错觉：会不会”这么顺利”是因为 A 恰好站在图的中央？为了排除这种怀疑，我们把起点换成 F，用完全相同的规则（邻居按字母顺序）再走一遍。

第 0 步：起点 F 入队，visited = {F}，队列 = [F]。

第 1 步：F 出队，访问 F（序号 1）。F 的邻居按字母顺序是 C、D、H，都没访问，依次入队。队列 = [C, D, H]。

第 2 步：C 出队，访问 C（序号 2）。C 的邻居是 A、E、F；F 已访问，A、E 没访问，依次入队。队列 = [D, H, A, E]。

第 3 步：D 出队，访问 D（序号 3）。D 的邻居是 A、F，都已访问，跳过。队列 = [H, A, E]。

第 4 步：H 出队，访问 H（序号 4）。H 的邻居是 F、G、I；F 已访问，G、I 没访问，依次入队。队列 = [A, E, G, I]。

第 5 步：A 出队，访问 A（序号 5）。A 的邻居是 B、C、D；C、D 已访问，B 没访问，入队。队列 = [E, G, I, B]。

第 6 步：E 出队，访问 E（序号 6）。E 的邻居是 B、C、G，全部已访问，跳过。队列 = [G, I, B]。

第 7 步：G 出队，访问 G（序号 7）。G 的邻居是 E、H，全部已访问，跳过。队列 = [I, B]。

第 8 步：I 出队，访问 I（序号 8）。I 的邻居只有 H，已访问，跳过。队列 = [B]。

第 9 步：B 出队，访问 B（序号 9）。B 的邻居是 A、E，已访问，跳过。队列 = []，结束。

整理成表：

步骤	出队访问	访问序号	出队后的队列	本次新标记
0（初始化）	—	—	[F]	F
1	F	1	[C, D, H]	C、D、H
2	C	2	[D, H, A, E]	A、E
3	D	3	[H, A, E]	无
4	H	4	[A, E, G, I]	G、I
5	A	5	[E, G, I, B]	B
6	E	6	[G, I, B]	无
7	G	7	[I, B]	无
8	I	8	[B]	无
9	B	9	[]	无

这次的分层是：F 距离 0；C、D、H 距离 1；A、E、G、I 距离 2；B 距离 3。对应的 BFS 树长这样：

graph TD
    F["F（0）"] --- C2["C（1）"]
    F --- D2["D（1）"]
    F --- H2["H（1）"]
    C2 --- A2["A（2）"]
    C2 --- E2["E（2）"]
    H2 --- G2["G（2）"]
    H2 --- I2["I（2）"]
    A2 --- B2["B（3）"]

两次走查放在一起看，有三点特别值得玩味。第一，算法完全没变，只是起点变了，访问顺序就完全不同：从 A 出发 B 排第 2 位，从 F 出发 B 排最后；这说明 BFS 的结果强烈依赖起点，描述它时必须说清”从谁出发”。第二，分层结构始终成立：无论起点是谁，访问顺序永远按距离分层推进，这是 BFS 的不变量。第三，图只有一张，BFS 树却有好多棵：每选一个起点，就长出一棵不同的 BFS 树；它们都是同一张图的”展开视图”，没有哪棵是唯一的。这个视角对理解后面”生成树”的概念也很有帮助。

3.6 手算自检清单

如果你在做题时遇到”BFS 结果和答案不一样”的困惑，按下面四步手算一遍，90% 的问题都能定位。

1. 固定邻居顺序：先把邻接表写出来，并约定每个顶点的邻居扫描顺序（比如按字母序或输入顺序）。每次手算都用同一个顺序，避免”这次先 B、下次先 C”的漂移造成结果对不上。
2. 初始化单独写一行：visited 含起点、队列含起点、dist[起点] = 0，这三件事缺一不可。缺了任何一件，第一轮就可能出错。
3. 每轮画两列：出队的是谁、新入队的是谁；每个新入队的顶点在入队前先打勾 visited。把这两列写下来，队列变化就一目了然。
4. 结束时核对数量：访问顺序的长度应该等于起点所在连通分量的顶点数；如果出现重复顶点，说明标记时机错了；如果漏了顶点，说明邻居遍历或连通性判断有误。

这份清单同样适用于调试代码：把每轮的队列打印出来，和手算表逐行对比，第一次分叉的地方就是 bug 所在地。手算不是浪费时间，它是在给代码”对表”。

4 visited：为什么图必须标记

4.1 不标记会怎样：先看一场事故

假设我们忘掉 visited，直接照搬树的层序遍历：队列从 [A] 开始，A 出队，把邻居 B、C、D 入队；B 出队，把邻居 A、E 入队；C 出队，把邻居 A、E、F 入队；D 出队，把邻居 A、F 入队……你发现问题了吗？A 被入队了三次，E 被入队了两次，F 被入队了两次。而且这还只是刚开始——等队列里的重复 A 出队时，它又会把 B、C、D 再入队一遍，新一轮重复雪崩式增长。这张图虽然很小，但队列会无限膨胀，程序永远跑不完。

把这场事故画出来，就是下面这个环形水流：

graph TD
    A["A 出队"] -->|"把 B、C、D 入队"| B["B 出队"]
    B -->|"又把 A 入队"| A
    B -->|"把 E 入队"| E["E 出队"]
    E -->|"又把 B 入队"| B
    C["C 出队"] -->|"又把 A、E 入队"| A
    C -->|"把 F 入队"| F["F 出队"]
    F -->|"又把 C、D 入队"| C

在这张图里，水波不是向外扩散，而是在同一个水池里互相倒灌：A 把 B 送进队列，B 又把 A 送回来；C 把 F 送进队列，F 又把 C 送回来。每一轮”回来”都会产生更多副本，队列越排越长，永远不会清空。这就是死循环（infinite loop）：不是算法写得慢，而是算法根本没有终止条件。

更隐蔽的是第二种危害：重复访问。就算图恰好没有环（比如一个有向无环图），同一顶点也可能被多条路径到达。假设有两条路都能到顶点 X，不标记的话 X 会被入队两次，被访问两次；如果 X 的邻居很多，每个邻居又会被重复处理……在路径数量呈指数增长的网络里（比如”爬楼梯”式的图），重复次数会爆炸。一个原本 O(V+E) 的算法，可能退化到根本跑不完。

4.2 visited 到底挡掉了什么

visited 的职责只有一条：保证每个顶点只被”发现”一次。它挡掉的不是”访问”，而是”重复发现”。有了它：

1. 入队唯一：一个顶点第一次被发现时入队，之后任何路径再碰到它都直接跳过，队列里永远没有重复顶点；
2. 访问唯一：每个顶点恰好出队一次，恰好被访问一次；
3. 算法必停：队列长度有上限（最多 V 个顶点），出队 V 次后队列一定为空；
4. 复杂度可控：总工作量 = 每个顶点出队一次的代价 + 每条边被检查一遍的代价，于是有了 O(V+E) 这个漂亮的上界。

换句话说，visited 不是”优化技巧”，而是正确性的一部分。少了它，BFS 在一般图上根本不成立。

4.3 什么时候可以省略 visited

有同学会问：既然 visited 这么重要，是不是所有 BFS 都必须带它？答案是：只要你能证明”每个顶点最多只会被发现一次”，visited 就可以省略。常见的合法场景有四类。

第一类：树和森林。树没有环，每个节点只有一个父亲，从根出发沿父子边走，任何节点都只会被它的父亲发现一次。这就是树系列层序遍历不需要 visited 的原因。注意，这里说的是”无环的树”；如果图里有环，哪怕只有一个，visited 就回来了。

第二类：明确的无环结构，比如链表、单入口的有向无环结构。你从 head 出发顺着 next 走，每个节点只有一条路能到达，天然不会重复。此时 BFS 退化成一次”按层扫描”，visited 可省。

第三类：用”父亲”信息代替全局标记。在无向树或网格这类无环结构里，BFS 出队 u 时，可以只把”不是 u 的父亲”的邻居入队。比如在树上，根的孩子入队时记住父亲是谁，处理孩子时跳过父亲，就不会走回头路。这相当于把全局 visited 换成”局部父亲指针”，仍然保证不重复。但在有环的图上，这招不够——环里的顶点没有唯一的父亲，还是需要全局标记。

第四类：只探索有限层数且层内天然无重复。比如某些状态搜索问题里，每一步的状态转换有严格的单向推进（状态只会”变大”或”变多”），同一状态不可能从两条路到达。这种情况很少见，而且一旦判断失误就会出 bug，所以我的建议是：除非你能在纸上写出”为什么不会重复”的完整证明，否则一律带上 visited。 带 visited 的代价只是 O(V) 的空间，换来的是确定性的正确，这笔买卖永远划算。

最后补充一个实现层面的小贴士：visited 不一定非要用独立的布尔数组。在第 6 章我们会看到，dist 距离数组可以兼任 visited——用 -1 表示”未访问”，用非负数表示”已访问且距离已知”。这样既省了一个数组，又顺便拿到了最短距离，一举两得。

还有一个容易混淆的细节：visited 只记录”是否被访问过”，本身不记录顺序；如果有人在发现顶点时顺手 push 进一个数组，得到的是”发现顺序”。好在 BFS 里入队顺序等于出队顺序，发现顺序和访问顺序天然一致，所以这种写法无伤大雅；但如果改成”出队时才标记”，两者就会分叉，调试时容易看花眼。明白这个区别，你能更快看懂别人代码里的微妙差异。

4.4 visited 的三种实现方式

既然 visited 这么重要，具体到代码里，它有哪几种”长相”？主要三种，各有各的适用场合。

第一种：布尔数组（boolean[]）。当顶点恰好是连续的整数 0 到 V-1 时，开一个长度 V 的布尔数组，visited[u] = true 表示已访问。这是最快、最省内存的写法：数组按下标随机访问是 O(1)，而且没有任何哈希开销。网格 BFS 里，还可以把二维坐标 (r, c) 编码成一维下标 r × 列数 + c，照样用一维数组。它的限制是顶点必须能映射成稠密整数，字符串顶点不行。

第二种：哈希集合（Set）。当顶点是字符串、对象或者不连续的自定义编号时，用 Set<string> 最自然。查找和插入都是期望 O(1)，写起来也最贴近”名单”的直觉：visited.has(v) 一眼看懂。代价是常数时间比数组大，内存占用也更高（每个元素还要存键本身）。顶点少的时候无所谓，顶点上百万时就要掂量一下。

第三种：距离数组兼任（dist + -1 哨兵）。初始化时把 dist 全部设为 -1，-1 就表示”未访问”；第一次发现顶点 v 时写入真实距离。判断”是否访问过”变成 dist[v] !== -1。这一种不但省一个数组，还免费送来了最短距离，是”最短路型 BFS”的标准写法。它的唯一代价是语义上稍微绕一点——你需要记住”-1 是未访问”这个约定，不能把 -1 当成真实距离。

三种方式选哪种，取决于顶点类型和题目要什么：只要访问顺序，布尔数组；顶点是字符串，Set；要最短距离，dist 兼任。无论选哪种，判断与标记的时机都遵守同一条铁律：入队前判断、入队时标记。

5 代码实现：邻接表版 JS/TS

5.1 先约定图的存储

第 3 篇讲过，邻接表是稀疏图的首选：每个顶点对应一个列表，列表里存着它的邻居。在 JavaScript / TypeScript 里，最自然的邻接表是一个 Map<string, string[]>，顶点用字符串表示；也可以用对象 Record<string, string[]>。下面的代码沿用第 3 篇的约定：graph.get(u) 返回 u 的所有邻居。

5.2 最简 BFS：只负责遍历

先写一个只做遍历、返回访问顺序的版本：

type Graph = Map<string, string[]>;

function bfsTraversal(start: string, graph: Graph): string[] {
  const visited = new Set<string>([start]);
  const queue: string[] = [start];
  const order: string[] = [];

  while (queue.length > 0) {
    const u = queue.shift()!;
    order.push(u);

    for (const v of graph.get(u) ?? []) {
      if (!visited.has(v)) {
        visited.add(v);
        queue.push(v);
      }
    }
  }

  return order;
}

这段代码一共二十行不到，我们逐行拆开看：

• const visited = new Set<string>([start])：用 Set 当 visited，初始就把起点放进去。为什么不初始化成空 Set 再把起点 add？因为”起点当然已访问”这件事必须从一开始就成立，否则第 1 步循环里起点自己可能被再次入队。
• const queue: string[] = [start]：队列用数组实现，起点入队。这里数组的左侧是队首。
• const order: string[] = []：结果数组，记录访问顺序，方便观察和调试。
• while (queue.length > 0)：循环终止条件是队列清空。结合 visited，这个循环最多执行 V 次。
• const u = queue.shift()!：取出队首。shift() 返回数组第一个元素并把它移除；! 是 TypeScript 的非空断言，告诉编译器”这里不会返回 undefined”。
• order.push(u)：访问 u——在这里，“访问”就是记录进结果数组。真实场景里可能是打印、计数、检查目标、更新距离。
• for (const v of graph.get(u) ?? [])：遍历 u 的所有邻居。?? [] 是防御性写法：如果某顶点没有登记在邻接表里，就当作没有邻居。
• if (!visited.has(v))：这是核心判断。邻居已经访问过，就跳过。
• visited.add(v); queue.push(v)：先登记、再入队。顺序不能反，原因见 2.4 节。

运行 bfsTraversal("A", graph)，返回的就是第 3 章手算出来的 ["A", "B", "C", "D", "E", "F", "G", "H", "I"]。你可以把这段代码抄进编辑器，把图的边补上，亲手跑一遍。想验证自己对代码的理解，可以做两个对比实验：第一，故意把 visited.add(v) 删掉，观察输出里出现重复顶点，亲手制造一次”死循环前兆”；第二，把 queue.shift() 换成 queue.pop()，观察访问顺序变成”一条道走到黑”，体会队列和栈的性格差异。这种对比实验比背十遍结论都管用。

5.3 进阶：按层处理

有时候我们不只是想要访问顺序，还想知道”第 0 层是谁、第 1 层是谁、第 2 层是谁”，比如迷宫题里要按层统计步数、二叉树题里要按层输出。这有一个经典技巧：在每一轮循环开始前，先快照当前队列的长度 size，然后只处理 size 个顶点。这一轮处理完的，就是完整的一层；这轮新入队的，全部留到下一轮。

function bfsByLayer(start: string, graph: Graph): string[][] {
  const visited = new Set<string>([start]);
  const queue: string[] = [start];
  const layers: string[][] = [];

  while (queue.length > 0) {
    const size = queue.length;          // 当前层的顶点数
    const layer: string[] = [];

    for (let i = 0; i < size; i++) {
      const u = queue.shift()!;
      layer.push(u);

      for (const v of graph.get(u) ?? []) {
        if (!visited.has(v)) {
          visited.add(v);
          queue.push(v);
        }
      }
    }

    layers.push(layer);
  }

  return layers;
}

关键在 const size = queue.length 这行：它必须在 for 循环之前执行。如果写在循环条件里（比如 for (let i = 0; i < queue.length; i++)），每处理一个顶点，queue 的长度都在变化，新入队的下一层顶点会被误当成当前层处理，层次就乱了。快照之后，for 循环只处理 size 个顶点，期间入队的顶点排在新队列尾部，下一轮自然轮到它们。

按层版本还有两个衍生用途。一是记录层号：每轮循环进入一次，就相当于层号加 1，所以 layers.length 减 1 就是当前层的距离，迷宫题可以直接用它当步数。二是统计每层顶点数：layer.length 就是这一层的宽度，想观察”扩散波峰”在哪一层，用它最方便。这个技巧在树系列的层序遍历里也有镜像版本，学过那篇的朋友应该会觉得亲切。

5.4 带距离和前驱的完整版

遍历只是热身。BFS 真正的威力在于它能顺便算出两样东西：每个顶点到起点的最短距离，以及最短路径上每个顶点的”上一个顶点”。升级版代码：

function bfsShortest(
  start: string,
  graph: Graph,
  target?: string
): { dist: Map<string, number>; prev: Map<string, string | null> } {
  const dist = new Map<string, number>();
  const prev = new Map<string, string | null>();
  const queue: string[] = [];

  dist.set(start, 0);
  prev.set(start, null);
  queue.push(start);

  while (queue.length > 0) {
    const u = queue.shift()!;
    if (u === target) break;

    for (const v of graph.get(u) ?? []) {
      if (!dist.has(v)) {
        dist.set(v, dist.get(u)! + 1);
        prev.set(v, u);
        queue.push(v);
      }
    }
  }

  return { dist, prev };
}

这个版本和遍历版的差别只有三处，但每一处都值得讲清楚。

第一，用 dist 兼任 visited：dist.has(v) 为 true 就说明 v 已经被发现过，等价于 visited。之所以可行，是因为 BFS 第一次发现一个顶点时，得到的距离一定是最短的——这个结论我们下一章证明。所以”已访问”和”距离已定”是同一件事，一个数组就够了。

第二，距离递推：dist.set(v, dist.get(u)! + 1)。v 是 u 的邻居，从起点到 v 的最短距离，等于从起点到 u 的最短距离加 1。因为 u 比 v 先被发现，所以算 v 时 u 的距离一定已经确定。

第三，前驱记录：prev.set(v, u) 记下”v 是被 u 发现的”。整张 prev 表合起来就是一棵 BFS 树。要还原从起点到任意顶点 t 的路径，只需要从 t 出发，沿着 prev 一路跳到起点，再把顺序反过来：

function restorePath(start: string, target: string, prev: Map<string, string | null>): string[] {
  const path: string[] = [];
  let cur: string | null = target;

  while (cur !== null) {
    path.push(cur);
    if (cur === start) break;
    cur = prev.get(cur) ?? null;
  }

  return path.reverse();
}

注意一个边界情况：如果 target 不在 dist 里，说明起点根本到不了 target，restorePath 会沿着 null 走到 path 里出现 null 为止。工程上更稳的写法是先检查 dist.has(target)，没有就直接返回空数组。为什么不会死循环？因为 prev 沿树的父指针一路向上，最终必然到达 prev 为 null 的起点——树没有环，这是结构保证的。

5.5 复杂度分析：O(V+E) 是怎么来的

现在到了每篇必谈的复杂度环节。先给结论，再给推导。

时间复杂度 O(V+E)，其中 V 是顶点数，E 是边数。

推导分两块。第一块，队列操作：每个顶点最多入队一次、出队一次（visited 保证），入队和出队都是 O(1)，所以队列部分合计 O(V)。第二块，邻居扫描：出队 u 时，我们会把 u 的整张邻居表扫一遍；把所有顶点的邻居表长度加起来，恰好等于 2E（无向图每条边贡献两个端点）或 E（有向图每条边贡献一个终点）。所以扫描部分合计 O(E)。两部分相加，就是 O(V+E)。

再回答一个常见疑问：为什么访问每个顶点时还要检查”邻居是否已访问”？因为每个顶点的邻居表必须完整看一遍才能不漏点，这是图遍历的底线工作。检查本身是 O(1)（Set 或数组下标），所以不拖后腿。

空间复杂度 O(V)：visited（或 dist）数组需要 V 个位置；队列最坏情况下容纳多少顶点？在”起点连接所有其他顶点”的星形图里，起点出队后队列里同时有 V-1 个顶点，所以队列是 O(V)。再加上邻接表本身的 O(V+E) 存储，如果只算算法附加空间，是 O(V)；把图本身的存储算进去，是 O(V+E)。

两个实现细节需要提醒。第一，JS 数组的 shift() 在引擎内部是 O(n) 的——每出队一个元素，后面所有元素都要往前挪。严格来说，用数组模拟队列的 BFS 最坏复杂度会变成 O(V²)。教学代码为了可读性保留 shift() 没问题，但追求性能时应改用”头指针 + 普通数组”（不真正删除元素，只移动下标）或者队列类。第二，如果图很大，Set<string> 的内存开销比布尔数组高；顶点恰好是 0..n-1 的整数时，用 boolean[] 或 Int8Array 更省。

5.6 邻接矩阵怎么办

如果图的存储是邻接矩阵（boolean[n][n]），BFS 骨架完全不变，只改一处：找邻居时不再遍历邻接表，而是扫描矩阵的第 u 行，看哪些格子是 true。扫描一行要 O(V)，每个顶点都要扫一行，所以矩阵版 BFS 的时间复杂度是 O(V²)，空间仍是 O(V)。稠密图（E 接近 V²）用矩阵版不亏，稀疏图还是邻接表版香——这个结论和第 3 篇的存储篇完全呼应。

5.7 为什么 BFS 很少用递归

看过树系列的朋友会问：DFS 可以轻松写成递归，BFS 为什么大家总写循环？原因有三层。

第一，BFS 的推进顺序是”横向”的，不依赖调用栈的”回溯”能力。递归擅长表达”先深入、再返回”的控制流，而 BFS 需要的控制流是”处理完一层再处理下一层”，用循环加队列表达最直接。

第二，递归实现 BFS 通常需要把队列作为参数层层传递，或者做成闭包共享，代码反而比循环版更绕。如果硬要递归，常见的写法是”递归处理一层”：函数接收当前层的顶点列表，生成下一层的顶点列表，再递归调用自己。这实际上是把队列换成了”分层列表”，可行，但不如循环优雅，也不如循环好调试。

第三，递归有函数调用栈深度限制，深度很大的图（比如一条十万个顶点的长链）可能触发栈溢出；循环版只占用堆内存，不存在这个问题。DFS 也有同样的隐患，所以工程上经常把 DFS 改成显式栈循环。结论一句话：BFS 就用队列循环，干净利落；递归的浪漫留给 DFS。

代码写完了，接下来是理论高光时刻：为什么 BFS 敢说”第一次遇到就是最短”？

6 BFS 的性质：分层访问与无权最短路径

6.1 性质一：访问顺序按层，距离非降

先给第一个性质下个准确定义：如果 BFS 的访问顺序是 u₁, u₂, u₃, …, uₖ，那么它们到起点的距离满足 dist(u₁) ≤ dist(u₂) ≤ … ≤ dist(uₖ)，并且任意时刻队列里相邻顶点的距离最多相差 1。

这个性质从手算走查里已经能看出来：A 的距离是 0，接着访问的 B、C、D 距离都是 1，再接着 E、F 距离是 2，然后 G、H 距离是 3，最后 I 距离是 4。数字一路从 0 涨到 4，从来没有”先访问距离 3 的，再回头访问距离 1 的”这种倒挂。

为什么必然如此？因为队列是 FIFO 的，而入队顺序天然按距离递增：起点距离 0 最先入队；只有距离 0 的顶点出队时，距离 1 的顶点才会入队；只有所有距离 1 的顶点都出队后，距离 2 的顶点才可能排到队首。用归纳的话说：先入队的顶点距离更小，后入队的顶点距离更大，所以出队顺序（也就是访问顺序）距离非降。队列里同时存在的顶点，最多跨两层：比如第 1 层只剩最后一个 D 时，队尾已经排进了第 2 层的 E、F，但第 3 层的 G、H 要等第 2 层全部出队才会入队。

这个性质是 BFS 一切应用的源头。把”距离”换成”层号”，把”顶点”换成”状态”，它就是”水波同步外扩”的严格表述。

6.2 性质二：第一次发现 = 最短距离

现在可以证明本篇最重要的定理：在无权图上从起点 s 出发做 BFS，当一个顶点 v 第一次被”发现”（入队）时，dist[v] 就等于 s 到 v 的最短路径长度。

证明用反证法，简洁有力。假设存在某个顶点 v，第一次被发现时记录的距离 d 不是最短距离，也就是说存在一条长度 d’ < d 的路径 s → … → v。沿着这条更短的路径走，路径上的第 d’ 个顶点 w 是 v 的邻居。因为 w 在路径上比 v 靠前，w 被发现的时间一定不晚于 v（这是”距离非降”的直接推论）——准确地说，w 会在 v 之前或同时出队。当 w 出队扫描邻居时，它一定会看到 v。如果 v 当时还没被访问，w 会以 dist[w]+1 ≤ d’ 的距离发现 v，与”v 第一次被发现的距离是 d > d‘“矛盾；如果 v 当时已被访问，那么它的距离只会更小，同样矛盾。所以不存在更短路径，d 就是最短距离。

这个证明的关键词是”同步外扩”：水波到达某个点的时候，所有比它近的点都已经先到达过了；任何一个更近的邻居都会抢在它之前把它”捞出来”。因此，BFS 第一次碰到目标时，直接就可以停下，不需要再搜下去——这就是”遇到就返回”的 BFS 最短路搜索的合法性依据。

6.3 用 dist 数组看分层

把第 3 章的图重新画一遍，这次在每个顶点旁边标上它到 A 的距离：

graph TD
    A["A（距离 0）"] --- B["B（距离 1）"]
    A --- C["C（距离 1）"]
    A --- D["D（距离 1）"]
    B --- E["E（距离 2）"]
    C --- E
    C --- F["F（距离 2）"]
    D --- F
    E --- G["G（距离 3）"]
    F --- H["H（距离 3）"]
    G --- H
    H --- I["I（距离 4）"]

请验证两个细节。第一，每条边的两端，距离差最多是 1：比如 E—G 是 2 和 3，F—H 是 2 和 3，H—I 是 3 和 4。这是 BFS 分层图的普遍规律：任何一条边连接的两个顶点，距离差不可能超过 1（否则就有一条更短的路）。第二，注意同一层的边也可能存在，比如 G—H 两个顶点的距离都是 3；而 D—F 这种跨层的边，两端距离分别是 1 和 2，差为 1。这说明”同一层”不代表”没有边”，分层不是把原图切成互不相连的块，只是按距离给每个顶点贴了标签。

如果我们把访问顺序也标上，就能看出”距离非降”和”序号递增”是同步的：序号 1 的 A 距离 0，序号 2–4 的 B、C、D 距离 1，序号 5–6 的 E、F 距离 2，序号 7–8 的 G、H 距离 3，序号 9 的 I 距离 4。距离相同的顶点，序号连成一段连续区间；层与层之间严丝合缝，没有交叉。

6.4 前驱数组与路径还原

光有距离还不够，面试和竞赛题还经常要求”把最短路径打印出来”。这时就要用到第 5.4 节的前驱数组 prev：每个顶点记录”我是被谁发现的”，整张表就是一棵 BFS 树。从目标往回走：I ← H ← F ← C ← A，把顺序反过来，得到 A → C → F → H → I，一共 4 条边，正是最短路径。

把还原过程画出来，红色加粗的路径就是答案（这里用文字标出重点边）：

graph TD
    A["A"] -->|"路径第 1 段"| C["C"]
    C -->|"路径第 2 段"| F["F"]
    F -->|"路径第 3 段"| H["H"]
    H -->|"路径第 4 段"| I["I"]
    A --- B["B"]
    B --- E["E"]
    E --- G["G"]
    G --- H
    C --- E
    D["D"] --- A
    D --- F

还原算法的代码在第 5.4 节已经给出，这里补三个易错点。第一，前驱要朝起点走，不是朝目标走：从目标出发，沿着 prev 一路向上，直到 prev 为 null（那一定是起点）。如果从起点往目标走，你会遇到岔路，不知道选哪条。第二，别忘了反转：我们是从目标倒着收集的，最终打印前要 reverse()。第三，只走 BFS 树边，不走原图边：原图里 C 还连着 E，但如果还原时走 C → E，就会得到一条绕远的路。还原的唯一合法依据是 prev 表，而不是原图的邻接表。

还有一个工程细节值得记住：如果只需要”最短路径长度”，可以不要 prev，只要 dist 数组；如果还需要”具体的某一条最短路径”，dist + prev 都要。如果只需要”目标是否可达”，连 dist 都可以不要，visited 就够。按需取用，别让代码背不必要的包袱。

6.5 从 A 到每个顶点的最短路径一览

把第 3 章那张九顶点图的 dist 和一条还原路径全部列出来，做成一张总表。这也是面试官最爱问的”给我讲讲 BFS 输出了什么”的标准答案：

顶点	距离	一条最短路径（按 prev 还原）
B	1	A → B
C	1	A → C
D	1	A → D
E	2	A → B → E
F	2	A → C → F
G	3	A → B → E → G
H	3	A → C → F → H
I	4	A → C → F → H → I

这张表里有几个值得停下来看一眼的细节。第一，距离相同的顶点，最短路径的长度相同，但路径形状千差万别：G 和 H 都是 3，G 走的是”左边”（A → B → E → G），H 走的是”右边”（A → C → F → H）。第二，表里的路径全部来自同一棵 BFS 树，它们彼此共享前缀：B 和 E 共享 A → B，C、F、H、I 共享 A → C → F。这不是巧合，而是 BFS 树的”树状前缀”结构——每个顶点的路径就是它父亲的最短路径加一条边。第三，BFS 只保证路径最短，不保证路径唯一：比如 D 的路径 A → D 是唯一的，但如果图里 A—D 和 A—C—D 都存在，两条都是最短路径，BFS 只会记下先发现的那条。需要”所有最短路径”的话，BFS 要改成记录所有可行的前驱，那是更进阶的玩法，本篇先不展开。

6.6 为什么 BFS 能找到无权最短路（再讲一遍）

刚才的证明比较紧凑，这里换一个更”物理”的角度再说一遍，帮你在直觉层面焊死它。

想象 BFS 是一支队伍从起点出发，每秒钟跨过一条边。第 0 秒，队伍在 A；第 1 秒，队伍里的士兵同时到达 B、C、D；第 2 秒，他们又同时到达 E、F；第 3 秒到达 G、H；第 4 秒到达 I。所有士兵的速度一样，所有边的长度一样（都是 1 条边），所以谁先到，谁走的路就最短。 如果某个顶点被第 3 秒的士兵到达了，那就不可能有第 2 秒甚至更早到达它的路线——否则第 2 秒就该有士兵站在那儿了。

“所有边长度一样”正是”无权图”的含义。一旦边有了权重（比如 A—B 是 5，A—C 是 1），“边数最少”和”总权重最小”就不再是一回事，BFS 的无权最短路结论立刻失效——那时候要请出第 5 篇之后会讲的 Dijkstra（戴克斯特拉）算法。这里先埋个伏笔，你只要记住边界：BFS 最短路只适用于无权图（或所有边权相同且非负的图，本质上等价于无权）。

6.7 BFS 树的一个副产品：可达性与连通分量

最后补充一个看起来顺理成章、但经常被忽略的应用。一次 BFS 从起点出发，能访问到的所有顶点，恰好是起点所在的连通分量（在第 2 篇我们讲过这个概念）。道理很简单：BFS 只能沿着边走，走得到的就是可达的；而所有可达顶点都会在 BFS 结束时被访问。所以：

function reachable(start: string, graph: Graph): string[] {
  return bfsTraversal(start, graph);
}

一个连通的无向图，从任意顶点出发 BFS 都能访问全部顶点；不连通的图，则需要从每个未访问的顶点各做一次 BFS，才能访问完全部顶点。这个”多次 BFS 数连通分量”的小技巧，是很多图论题的底层模板，后面讲 DFS 时会再次遇到它的镜像版本。

6.8 拓展：BFS 与树的直径

BFS 按层扩散还有一个衍生玩法：求”最远有多远”。从一个顶点出发做 BFS，最后一个被访问的顶点的距离，就是”离它最远的顶点有多远”。如果对每个顶点都做一次 BFS 取最大距离，就得到了图的离心率与直径（图上最远两点的距离）。

朴素做法的复杂度是 O(V(V+E))，对大树来说太贵。但在树这种特殊图上有一个著名技巧：随便选一个点做 BFS，找到离它最远的点 u；再从 u 做一次 BFS，找到离 u 最远的点 v；u 到 v 的距离就是树的直径。两次 BFS 搞定，复杂度 O(V)。这个结论依赖树的无环性质，在一般图上不成立——有环时”最远点”可能不稳定，算法会给出错误答案。树的直径是树系列和竞赛题里的经典内容，等我们讲完 DFS，可以专门回头用它练手。

顺带一提，“最后一个被访问的顶点”这个说法在 BFS 里是准确的：因为访问顺序按层推进，队列里最后出队的顶点，一定处于最深的某一层。这也是 BFS 队列性质的一个意外福利。

6.9 dist 只写一次，为什么安全

很多人在学完带权最短路算法（比如 Dijkstra）之后回看 BFS，会冒出一个疑问：Dijkstra 里同一个顶点的距离可能被更新多次（专业说法叫”松弛”），BFS 里为什么 dist[v] 只在第一次发现时写一次就够了？

答案就藏在”边权统一”四个字里。Dijkstra 的边权各不相同，后到达的路径总权重可能更小，所以必须反复松弛；而 BFS 的每条边代价都是 1，后发现的路径不可能比先发现的更短——因为先发现的路径层数更少，第 6.2 节的定理已经证明这一点。因此 dist[v] 一旦写入，就永远是最优值，不需要第二次更新。

这也解释了为什么 BFS 代码里不需要”比较取小”这个动作：如果写 dist[v] = Math.min(dist[v], dist[u] + 1)，结果碰巧也正确，但那个 min 是永远不生效的冗余代码——它试图解决的问题在无权图里根本不存在。认清这一点，你就能把 BFS 和带权最短路算法的边界划得干干净净：BFS 靠”第一次就是最优”吃饭，带权算法靠”反复松弛直到收敛”吃饭。

理论篇到此结束。接下来进入实操环节，看 BFS 在四个经典场景里怎么发光发热。

7 经典应用：从迷宫到单词接龙

7.1 应用一：迷宫最短步数

迷宫是最直观的 BFS 应用。把迷宫看成一张图：每个格子是一个顶点，相邻的可通行格子之间有一条边。从起点格子出发做 BFS，第一次到达终点格子时走过的层数，就是最短步数。为什么能这么转化？因为每一步移动恰好消耗 1 步，整张图是无权图，“步数最少”就是”边数最少”，正中 BFS 的射程。

举个 4×4 的小迷宫，S 是起点，T 是终点，黑色方块是墙，白色方块可通行：

graph TD
    S((S)) --- A1((A))
    A1 --- A2((A2))
    A2 --- A3((A3))
    A3 --- A4((A4))
    A4 --- T((T))
    A1 --- B1((B1))
    B1 --- B2((B2))
    B2 --- T

等等，这个”迷宫”画得不够像迷宫——它其实是一张抽象的通道图，每个节点代表一个可通行格子。真实迷宫通常是网格，但抽象之后就是这样的图。从 S 出发 BFS：S 距离 0，A、B1 距离 1，A2、B2 距离 2，A3 距离 3，A4 距离 4，T 距离 4（经 A4 到达）或距离 3（经 B2 到达）。第一次碰到 T 时它的距离是 3，所以最短路径是 S → B1 → B2 → T，一共 3 步。注意，如果继续把 BFS 跑完，T 还会被另一条路（S → A → A2 → A3 → A4 → T）再次发现，但因为”先登记再入队”，第二次发现直接被跳过，dist[T] 永远停留在第一次的 3。

在真实代码里，迷宫通常不会真的建一张邻接表，而是直接在二维数组上做 BFS：用队列存坐标 [row, col]，每次出队后向上下左右四个方向试探，越界或撞墙就跳过。这套”网格 BFS”模板是算法题的高频考点，核心还是那个四步循环，只是”邻居”从邻接表变成了四个方向。这里有一个细节：第一次碰到终点就可以 return dist，因为 BFS 的性质保证第一次就是最短；不用等队列清空。这也是 BFS 题和”全部遍历”题的唯一区别——前者可以提前终止，后者必须跑完。

举一个 3×3 的具体例子，. 是可走格，# 是墙，S 是起点，T 是终点：

S . .
. # .
. . T

把格子标上坐标（行，列）：S 在 (0,0)，T 在 (2,2)，墙在 (1,1)。BFS 的扩散过程是：S 距离 0；它的邻居 (0,1) 和 (1,0) 距离 1；(0,2) 和 (2,0) 距离 2；再往外是 (1,2) 和 (2,1) 距离 3；最后 T (2,2) 距离 4，可以从 (1,2) 或 (2,1) 到达。第一次出队到 T 时，答案就是 4 步，程序立刻返回。注意，如果你忘了 visited，两个方向的水波会在 (2,2) 相遇后互相倒灌——(1,2) 把 T 入队，T 出队后又会把 (2,1) 入队，队列永远清不空。visited 在网格题里同样是生命线。

网格 BFS 的代码骨架长这样：

function mazeMinSteps(
  maze: string[][],
  start: [number, number],
  target: [number, number]
): number {
  const rows = maze.length;
  const cols = maze[0].length;
  const dist: number[][] = Array.from({ length: rows }, () => Array(cols).fill(-1));
  const queue: [number, number][] = [start];
  dist[start[0]][start[1]] = 0;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  while (queue.length > 0) {
    const [r, c] = queue.shift()!;
    if (r === target[0] && c === target[1]) return dist[r][c];

    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (maze[nr][nc] === '#') continue;
      if (dist[nr][nc] !== -1) continue;
      dist[nr][nc] = dist[r][c] + 1;
      queue.push([nr, nc]);
    }
  }

  return -1; // 不可达
}

这段代码是”dist 兼任 visited”的教科书式示范：dist 初始全 -1，既当访问标记又当距离表；四个方向试探时，先判越界、再判墙、再判是否访问过，三层过滤缺一不可。return -1 表示终点不可达——这也是 BFS 的一个隐性优点：它不仅能求最短距离，还能顺便判断”是否可达”。

7.2 应用二：多源 BFS——多个水波同时扩散

现实里经常有”多个起点”的问题：地图上有好几家便利店，想知道每个居民区离最近的便利店有多远；果园里有几个腐烂的橘子，想知道所有橘子多久会全部腐烂；城市里有几个消防站，想知道每个街区离消防站多近。这些问题的共同点是：距离是”到最近的那个源”的距离，而不是到某个固定源的距离。

解法简单得让人惊讶：把所有源点一开始就全部放入队列，距离都记 0，然后正常做 BFS。多个水波同时扩散，谁先碰到某个格子，谁就是离它最近的源；格子的 dist 值就是它到最近源的距离。为什么正确？因为 BFS 的距离非降性质不依赖”只有一个起点”——多个起点只是让第 0 层有多个顶点，队列依然按距离递增推进，第一个碰到顶点 v 的波一定来自最近的源。

画一张图感受一下。图里有三个源点 X、Y、Z（距离 0），它们的水波同时扩散：

graph LR
    subgraph 第0层["第 0 层：三个源点同时入队"]
        X["X（0）"]
        Y["Y（0）"]
        Z["Z（0）"]
    end
    subgraph 第1层["第 1 层"]
        X1["X1（1）"]
        Y1["Y1（1）"]
        Z1["Z1（1）"]
        M["M（1）"]
    end
    subgraph 第2层["第 2 层"]
        N["N（2）"]
        O["O（2）"]
    end
    X --- X1
    Y --- Y1
    Z --- Z1
    X1 --- M
    Y1 --- M
    M --- N
    Z1 --- O
    N --- O

注意 M：它同时被 X1 和 Y1 连接，但只会被先出队的那一个发现一次，dist[M] = 1。N 和 O 之间的距离是 2，如果 N 先被 M 发现，O 之后也会被 N 或 Z1 发现，谁先到都行，dist 都是 2。多源 BFS 的复杂度依然是 O(V+E)，和单源完全一样——增加源点不增加任何额外开销，这是它比”对每个源分别做一次 BFS”高明的地方。如果对每个源分别 BFS，复杂度会变成 O(K(V+E))，K 是源点个数，在 K 很大时不可接受。

多源 BFS 的代码只需要改两行：初始化时不是 queue.push(start)，而是 for (const s of sources) { dist.set(s, 0); queue.push(s); }。其余循环体一个字都不用改。这种”只改初始化、不改主循环”的优雅，正是把问题抽象成图之后才有的红利。

7.3 应用三：单词接龙

单词接龙是 LeetCode 上的经典题（题目名 Word Ladder）：给定一个起始单词、一个结束单词和一个单词表，每次只能改变一个字母，要求从起始单词变成结束单词，问最少需要几步。比如 hit → hot → dot → dog → cog，每次改一个字母，一共 4 步（如果算上起始单词是 5 个词）。

怎么变成 BFS？把每个单词看作一个顶点，如果两个单词恰好差一个字母，就在它们之间连一条边，这样图就建好了。起始单词是起点，结束单词是目标，边的权全是 1，所以”最少变换步数”就是”最短路径长度”，BFS 完美接管。下面是一小段单词图的示例：

graph LR
    hit["hit"] --- hot["hot"]
    hot --- dot["dot"]
    dot --- dog["dog"]
    hot --- pot["pot"]
    dot --- lot["lot"]
    lot --- log["log"]
    dog --- log
    dog --- cog["cog"]
    log --- cog

从 hit 出发 BFS：hit（0）→ hot（1）→ dot、pot（2）→ dog、lot（3）→ cog、log（4）。第一次碰到 cog 时距离是 4，对应路径 hit → hot → dot → dog → cog，正是最短变换。注意这张图里到 cog 还有别的路（hit → hot → dot → lot → log → cog，5 步），但 BFS 只关心最短的那条。

建图有一个常见的优化：不要两两比较所有单词（O(N²) 会超时），而是对每个单词的每个位置，把该位置替换成通配符（比如 h*t、h_t），再用哈希表把”通配符模式”映射到单词列表。这样 BFS 找邻居时，只需要查 3 个（单词长度的）通配符键，复杂度降为 O(N×L)，L 是单词长度。这个技巧背后其实是”隐式建图”——图不预先全部建好，而是在 BFS 过程中按需生成邻居，下一节的状态空间搜索也会用到同样的思路。

7.4 应用四：状态空间搜索（八数码）

最后一个应用把”图”的概念推向极致：图不一定是”存好的”，也可以是搜索过程中动态展开的。八数码问题（8-puzzle）就是典型例子：3×3 的棋盘上有 8 个数字方块和一个空格，每次可以把空格相邻的方块滑进空格，问从初始排列到目标排列最少要滑几次。

在这里，每个棋盘排列是一个顶点，一次滑动是一条边。初始排列是起点，目标排列是终点，边的权都是 1，所以最少滑动次数又是 BFS 的最短路径。图有多大？9! = 362880 个排列，对 BFS 来说完全在可控范围内。你不需要把 36 万个顶点提前画出来，只需要在 BFS 出队一个排列时，现场生成它的 2–4 个邻居（空格向四个方向滑动），再查 visited（这里可以用”排列的字符串”作为键）即可。这种”按需生成邻居”的 BFS，就叫状态空间搜索，是八数码、华容道、魔方、拼图类问题的统一模板。一句话总结：**凡是”状态 + 一步转移”且”每步代价相同”的问题，都可以试着用 BFS 搜出最少步数。**八数码还有一个工程细节：判重时把排列编码成 9 位字符串或整数（比如 123456780），比直接比较二维数组快得多，这就是”状态压缩”的雏形；当状态空间大到哈希表都吃力时，还可以用康托展开给每个排列一个唯一编号，改用布尔数组判重。这些属于状态搜索的进阶技巧，本篇先记住名字和用途即可。

7.5 应用五：社交网络里的六度分隔

第 1 篇提到过”六度分隔”理论：据说世界上任意两个人之间，平均只需要几个中间人就能建立联系。如果把”人”当顶点、“好友关系”当边，那么”你和目标之间隔几个人”就是图上的一条最短路径问题，BFS 正好是它的天然解法。

设想一个百万用户级的社交网络：从你出发做 BFS，第 1 层是你的全部好友，第 2 层是好友的好友，第 3 层是好友的好友的好友……每扩展一层，覆盖的人数通常呈指数增长（这就是社交网络的”爆炸式传播”）。当 BFS 第一次碰到目标用户时，层号就是”你们之间隔了几层”，返回路径还能顺带告诉你”应该通过谁去搭上线”。现实中”好友推荐""可能认识的人”这类功能，背后往往就有 BFS 的身影：从你出发扩展两三层，把新出现的、和你还互不相识的顶点推荐给你。

社交网络场景还带出一个工程问题：图太大，BFS 的层数往往不用跑满。如果只需要”3 度以内的人”，可以给 BFS 加一个最大层数限制，超过 3 层就停止。这种”限层 BFS”在实际系统里非常常见，它用”少跑几层”换来了可接受的耗时。

7.6 变体预告：双向 BFS

最后介绍一个进阶变体，给爱钻研的朋友留个钩子：双向 BFS（Bidirectional BFS）。当起点和目标都明确时（比如迷宫两端、单词接龙的两个单词），可以同时从起点和目标各做一次 BFS，两股水波相向而行，在中途相遇时，把两边的距离加起来，就是最短路径长度。

为什么双向更好？如果单向前进每层扩展 b 个顶点、需要 d 层，单向 BFS 要访问大约 b^d 个顶点；双向各走 d/2 层，两边合计大约 2 × b^(d/2) 个顶点。当 b 和 d 都很大时，这个差距是指数级的——比如 b=10、d=8 时，单向要访问上亿量级的顶点，双向每边只有一万多，快得不是一点半点。双向 BFS 的细节（如何判断相遇、如何还原整条路径）有点讲究，属于”搜索进阶”的内容，今天先记住它的存在和它解决的问题，未来专题里我们再展开。

7.7 多源 BFS 的代码骨架

7.2 节讲了多源的思想，这里补上可以直接套用的代码骨架。经典题目”01 矩阵”：给定一个 0/1 矩阵，求每个格子到最近的 1 的距离。解法就是把所有值为 1 的格子当作源点，同时入队、距离 0，然后向四周扩散：

function nearestOne(grid: number[][]): number[][] {
  const rows = grid.length;
  const cols = grid[0].length;
  const dist = Array.from({ length: rows }, () => Array(cols).fill(-1));
  const queue: [number, number][] = [];

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 1) {
        dist[r][c] = 0;
        queue.push([r, c]);
      }
    }
  }

  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  while (queue.length > 0) {
    const [r, c] = queue.shift()!;
    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (dist[nr][nc] !== -1) continue;
      dist[nr][nc] = dist[r][c] + 1;
      queue.push([nr, nc]);
    }
  }

  return dist;
}

和单源版本对比，唯一的区别在初始化：单源是”一个点距离 0 入队”，多源是”所有源点距离 0 全部入队”。主循环一个字没改。第一次把这段代码写对之后，你会在心里感慨：BFS 的通用性，正是来自”把问题抽象成图”这一步；一旦图建好了，算法本身不关心起点有几个。

7.8 现实世界里的 BFS

最后看一眼 BFS 在工程里的身影，你会发现它无处不在。

网络爬虫从首页出发，按链接一层一层抓取，是 BFS 的经典应用——搜索引擎希望优先抓取”离首页近”的页面，这正是按距离优先。P2P 下载和区块链网络里，消息从发起节点向全网邻居广播，每经过一跳就多一层，本质是”多源限层 BFS”的变体。网络路由计算”到达某个目的地的跳数”时，跳数就是无权最短路径，BFS 的思路依然活跃。推荐系统里的”二度人脉""可能感兴趣的人”，也常常是社交图上两三层 BFS 的产物。

这些系统里的图动辄上亿顶点，直接做完整遍历太贵，所以工程版本普遍会加上限层、抽样、分区等优化；但不管怎么优化，队列、visited、按层推进这三个骨架从未变过。理解 BFS 的本质，就等于理解了这些系统的第一性原理。

到这里，BFS 的正餐已经吃完。最后用一章的篇幅，把它和它的老对手 DFS 放在一起预告一下，为第 5 篇铺好路。

8 预告：DFS 与 BFS 的世纪对望

如果 BFS 是”水波”，那深度优先搜索（DFS，Depth-First Search）就是”钻地鼠”：它不满足于一圈一圈扩散，而是选定一条路一头扎进去，一直走到走不动为止，再退回来换下一条路。树系列的读者对这个形象不陌生——前序遍历、中序遍历、后序遍历都是 DFS 在二叉树上的表现，它们共用同一个递归骨架。下一篇（图系列第 5 篇）会把 DFS 完整展开：递归实现、显式栈实现、visited 的用法、以及在找环、拓扑排序、强连通分量里的种种妙用。

今天只做一次”对望”，把两个算法并排放在一起，看看它们的精神气质有什么不同：

graph LR
    subgraph BFS_side["BFS：水波扩散"]
        B1["访问起点"]
        B2["处理第 1 层全部"]
        B3["处理第 2 层全部"]
        B1 --> B2 --> B3
    end
    subgraph DFS_side["DFS：一路到底"]
        D1["访问起点"]
        D2["沿第一条路走到头"]
        D3["回溯换第二条路"]
        D1 --> D2 --> D3
    end

五个关键差异，提前记在小本本上：

1. 数据结构：BFS 用队列（FIFO），先来先服务；DFS 用栈（LIFO），后进先出——递归的函数调用栈本质上就是栈。
2. 访问顺序：BFS 按层推进，距离非降；DFS 按”一条路径先走完”推进，访问顺序与距离无关。
3. 最短路：无权图上 BFS 能找到最短路径，DFS 找到的通常只是”某一条路径”，不一定最短。
4. 空间：BFS 的队列在”宽度大”的图里可能很占空间（最坏 O(V)）；DFS 的栈深度最坏也是 O(V)，但在”深度大、宽度小”的图（比如一条长链）里，DFS 可以借助尾递归或显式栈更省心。两者最坏空间同为 O(V)，但实际峰值出现在不同的图形态上。
5. 适用场景：BFS 偏爱”最少步数、最近距离、逐层扩散”；DFS 偏爱”是否存在路径、全排列、连通块染色、找环、拓扑排序”。

一句话预告：当你听到”最短""最少""最近”时，优先想 BFS；当你听到”是否存在""全部方案""路径打印”时，DFS 往往是更顺手的工具。 下一篇我们会把 DFS 的每个角落都翻一遍，届时再回头对比，你会对这对兄弟有更完整的认识。

8.1 三个常见误区

在预告的最后，顺手拆掉三个关于 BFS 的常见误区，免得你带着错误印象进入第 5 篇。

误区一：BFS 一定比 DFS 快。 两者时间复杂度同为 O(V+E)，“快不快”取决于问题本身。求无权最短路，BFS 是对的工具；但只问”是否存在一条路径”时，DFS 常常更早命中目标，不需要像 BFS 那样先铺满一整层。工具没有高下，只有合不合适。

误区二：visited 只是防死循环的保险丝。 它同时也是复杂度 O(V+E) 的保证、dist 正确性的前提、连通分量统计的基础。少了 visited，BFS 连”正确”都谈不上，更不用说”高效”。

误区三：BFS 只适用于无权图。 更准确的说法是：BFS 的最短路结论要求”每条边的代价相同”。如果所有边权相同（比如都是 5），把”每条边”当成”5 个等长的子步骤”来看，BFS 的结论依然成立；只有当边权各不相同、且你需要”总权重最小”时，BFS 才让位给 Dijkstra 等算法。判断的标准不是”图有没有权”，而是”代价是否统一”。

还有一个小技巧送给你：面试里如果题目要求”最小步数""最短距离""按层处理”，先说出”BFS + 队列 + visited + dist”这四件套，再确认图是否无权、起点是否有多个、是否允许提前终止。 这四连问能帮你把八成模板题瞬间归类，剩下的细节只是填空。

8.2 边界情况与实现细节

最后一节，把 BFS 最容易在极端数据上翻车的场景集中扫一遍。

自环与重边。 自环是”自己连自己”的边，比如 A—A。BFS 处理 A 时看到邻居 A，visited 里已经有 A，直接跳过，没有任何问题。重边是”两个顶点之间有多条边”，比如 A—B 出现两次；邻接表里 B 出现两次，第一次入队后 visited 挡住第二次，同样没问题。所以自环和重边对 BFS 是”无害冗余”，只是会浪费一点扫描时间；追求极致时，建图阶段可以去重。

孤立顶点。 一个没有邻居的顶点，从它出发的 BFS 只访问它自己，队列瞬间清空，行为正确。它也不会干扰其他连通分量的遍历，这正好是”多次 BFS 数连通块”的基础。

起点就是目标。 这里很容易写错：如果起点和目标是同一个顶点，最短距离是 0，路径就是 [起点]。正确的做法是在出队后、扩展邻居前检查目标，那么起点出队时立刻返回 dist = 0，天然正确；如果把目标检查放在扩展之后，就会漏掉这个答案，或者返回一个错误的更大值。

目标不可达。 BFS 跑完整个连通分量也没碰到目标，最后队列清空退出。此时要返回”不可达”信号（-1 或 null），而不是假装找到。这个分支容易忘，写代码时记得补上。

空图与未知起点。 起点不在邻接表里时，graph.get(u) 返回 undefined，我们的 ?? [] 兜底让代码优雅处理：visited 依然记录起点，输出只有起点一个顶点。顶点数 V 为 0 的空图，BFS 直接返回空结果，不需要特殊分支。

大图优化。 visited 用布尔数组、队列用头指针、dist 用整数数组，都是大图场景的常规手段。另外，BFS 是天然的”边搜边建”算法：它不需要预先知道整张图，邻居可以在出队时现场生成，这对状态空间搜索尤其重要——八数码的图就是这么隐式展开的。

9 要点速查表

把本篇所有干货压缩进一张表，方便你复习和面试前快速过一遍：

项目	内容
核心思想	从起点出发，按距离逐层扩散，先访问近的，再访问远的
核心数据结构	队列（FIFO），配合 visited 访问标记
标记时机	入队时立即标记，避免重复入队与死循环
伪代码骨架	初始化入队 → 循环：出队访问 → 未访问邻居入队 → 直到队列为空
时间复杂度	O(V+E)（邻接表）；O(V²)（邻接矩阵）
附加空间	O(V)：visited/dist 数组 + 队列
访问顺序性质	按层访问，距离非降，队列中相邻顶点距离差 ≤ 1
无权最短路	第一次发现顶点时，其距离即为最短距离；配 prev 数组可还原路径
多源扩展	所有源点初始全部入队，距离 0，其余代码不变
可提前终止	找目标最短路时，目标第一次出队即可返回
省略 visited 的条件	能证明每个顶点最多被发现一次（树、无环结构、显式父指针）
常见应用	迷宫最少步数、多源最近距离、单词接龙、八数码状态搜索、连通分量统计

这张表怎么用？第一，复习时按行自查，每一行都要能用一分钟讲清楚，讲不出来就翻回对应章节看配图；第二，做题时先核对”核心思想”和”标记时机”两行，确认模板没有写偏；第三，遇到”最短、最少、最近”的题，先判断图是否无权，再决定 BFS 是否适用。把这十二行内容装进脑子，BFS 的主体就算真正掌握了。

10 自测题

11 下一篇预告

这一篇我们把”广度”走完了：水波扩散的直观、队列 + visited 的机制、手算走查、无权最短路、四大应用，全部配图讲透。但遍历的世界还有另一半——深度优先搜索（DFS）。下一篇《图系列第 5 篇：深度优先搜索 DFS》，我们会从递归与栈的视角重新出发：DFS 的三种序、显式栈写法、找环与拓扑排序、强连通分量，还有它和 BFS 在无数题目里的分工合作。如果说 BFS 是”逐层逼近的狙击手”，那 DFS 就是”逢山开路的探险家”；把两者都握在手里，你的图论工具箱才算真正配齐。

我们下一篇见。