1.6 广度优先搜索

从这一篇起，我们进入图的世界。前面学的排序、查找、哈希，处理的都是"一堆独立的元素"；图不一样，元素之间有关系（边），算法要在这个关系网里找路、找结构。图遍历是所有图算法的地基，而图遍历有两种基本姿态——广度优先（BFS，本篇）和深度优先（DFS，下一篇）。先把 BFS 讲透。

1.BFS 的直觉：一圈一圈往外扩

想象你站在地图上一个点，想知道走到其他各点最少要几步。你怎么探？先把一步能到的所有点全走一遍，再把两步能到的全走一遍，再三步…… 一层一层、一圈一圈地往外扩。

这就是广度优先搜索（Breadth-First Search）的精髓：先广后深，按距离层层推进。它天然能回答"从起点到某点最少走几步"——因为你是一圈圈扩的，第一次到达某点时，经过的步数就一定是最少的。

BFS(G, s)                    // 图 G，起点 s
    for each vertex u in G:
        u.dist = ∞, u.parent = NIL
    s.dist = 0
    Q = {s}                   // 队列，先进先出
    while Q 非空:
        u = Q.dequeue()
        for each neighbor v of u:
            if v.dist == ∞:   // 没访问过
                v.dist = u.dist + 1
                v.parent = u
                Q.enqueue(v)

注意那个队列 $Q$——BFS 用队列（先进先出）是关键。新发现的节点排到队尾，处理时从队头取，这就保证了"同一层的全处理完，才处理下一层"。下一篇你会发现 DFS 用的恰恰相反——是栈（后进先出）。队列 vs 栈，正是 BFS vs DFS 的全部差别。

2.BFS 能干什么

BFS 这一套"层层扩展"的过程，顺带产生了两个有用的副产品：

最短路径（无权图）。 因为是按距离一层层扩的，v.dist 记录的就是起点到 $v$ 的最少边数，v.parent 串起来就是一条最短路径。想找无权图里 A 到 B 的最短路线？BFS 一次就给你。带权图的最短路要等 3.4 节的 Dijkstra，但无权图 BFS 就够了。

连通分量与层数。 从一个点 BFS，能走到的所有点构成一个连通分量。BFS 的层数就是图的"半径"信息——社交网络里"你和某人间隔几个人"（六度分隔），就是 BFS 的层数。

3.复杂度

每个顶点入队出队各一次，每条边在无向图里被检查两次（有向图一次）。所以 BFS 的复杂度是 $O(V+E)$（$V$ 是顶点数，$E$ 是边数）。注意这是线性于图的大小的——遍历整个图，每个点和每条边只花常数时间，非常高效。后面几乎所有图算法的复杂度都是 $O(V+E)$ 或它的倍数。

4.BFS 的脾性：找最短，但不省内存

BFS 的强项是保证找到最短路径（无权图），代价是内存——它要把同一层的所有节点都存进队列。如果图的"分支很多"（每个节点邻居很多），队列会膨胀得很快。想象一棵分支因子为 $b$、深度为 $d$ 的树，BFS 在找到目标前，队列里最多同时存约 $b^d$ 个节点——指数级。这就是下一篇 DFS 相对 BFS 的优势：DFS 的内存只正比于深度 $O(d)$，因为它一条路走到黑，不用横向铺开。

BFS：最短路径的保证者，内存的吞金兽。DFS：内存省、走得深，但不保证最短。 各有所长，看你最在乎什么。

5.练习

Q1. BFS 为什么用队列而不是栈？换成栈会变成什么？

BFS 的本质是"先处理同一层的，再处理下一层"，队列的先进先出恰好保证这一点——先发现的（同层）先被处理。换成栈（后进先出），就会变成"刚发现的下一个马上处理"，也就是沿着一条路一直走到底——那就成了 DFS（下一篇）。队列 vs 栈，是 BFS vs DFS 的分水岭。

Q2. 在无权图里用 BFS 找最短路径，为什么第一次到达某点时的距离就一定是最短的？

因为 BFS 按距离层层扩展：先访问所有距离为 1 的点，再 2，再 3……第一次访问到某点时，它所在的层数就是当前扩展的距离，而所有更近的层都早已被处理完，不可能有更短的路径还没被发现。所以第一次到达即最短。

Q3.（思考题） BFS 在分支因子很大的图上内存开销大（队列存 $O(b^d)$）。什么样的场景下这个缺点致命？

当图很"宽"（每个节点邻居多）且目标藏得较深时，BFS 的队列会指数膨胀，内存撑不住。比如棋类游戏的搜索树（每个局面有几十种走法），BFS 几层就爆内存。这种场景下人们更倾向 DFS 或带剪枝的搜索（9.7 分支定界）。反过来，如果图的宽度有限、或者你必须要最短路径，BFS 就值得这点内存代价。

6.小结

广度优先搜索用队列一圈圈扩展，能在线性时间 $O(V+E)$ 内遍历图、并在无权图里求出最短路径。它的强项是"最短路径保证"，软肋是"内存随宽度指数增长"。下一篇我们看它的镜像——深度优先搜索，它会用栈一路走到底，换来省内存和另一种独特的本事。