广度优先搜索

Views: --

广度优先搜索（BFS）从源点开始，先访问距离为 1 的顶点，再访问距离为 2 的顶点，像水波一样逐层向外扩散。

1. 核心数据结构是队列

for each vertex v:
    distance[v] = infinity
    parent[v] = NIL
distance[s] = 0
queue.push(s)

while queue is not empty:
    u = queue.popFront()
    for each v in Adj[u]:
        if distance[v] == infinity:
            distance[v] = distance[u] + 1
            parent[v] = u
            queue.pushBack(v)

顶点第一次被发现时就立即标记，而不是等出队时再标记。否则同一顶点可能被多个邻居重复入队。

2. 队列为什么带来“按层”顺序

源点先入队。距离为 kk 的顶点出队时，它发现的未访问邻居距离为 k+1k+1，并被放在当前队尾。因此队列中的距离最多相差 1，且从队头到队尾不下降。

这条不变量保证顶点第一次被发现时，找到的就是边数最少的路径。

3. 无权最短路

在每条边代价相同的图中，BFS 计算

distance[v]=δ(s,v),distance[v]=\delta(s,v),

即从源点 ss 到 vv 的最少边数。沿 parent 从目标回溯到源点，再反转，就得到一条最短路径。

若边权不同，即使都非负，也不能使用普通 BFS；需要 Dijkstra。只有权重全为 1，或能等价转成逐层状态时，BFS 的最短路结论才成立。

4. BFS 树

所有 parent 边构成以 ss 为根的 BFS 树。树中每个顶点深度等于其最短距离。

最短距离唯一，但最短路径可能不唯一；邻接表的遍历顺序不同，得到的父结点和 BFS 树也可能不同。

5. 复杂度

使用邻接表时，每个顶点最多入队一次，每条边被检查常数次：

T=O(V+E),S=O(V).T=O(V+E),\qquad S=O(V).

无向边会从两个端点各检查一次，仍为 O(E)O(E)。使用邻接矩阵时，每个顶点都扫描一整行，时间为 O(V2)O(V^2)。

6. 非连通图

从单一源点 BFS 只访问其可达部分。若要遍历整张无向图、统计连通分量，应对每个尚未访问的顶点启动一次 BFS；每启动一次就得到一个新的连通分量。

7. 二分图判定

把源点染为 0，BFS 每走一条边就给邻居染相反颜色。若遇到一条边连接同色顶点，图不是二分图。

这本质上按距离奇偶分层。无向图可二分当且仅当没有奇环。非连通图要从每个未染色顶点分别启动。

8. 网格最短路

迷宫和棋盘题常把每个可走格子视为顶点，上下左右移动视为边。BFS 模板不变，只是邻接关系由坐标现场生成。若状态还包含钥匙、方向或剩余次数，应把它们一起放进顶点状态；只记录坐标会错误合并不同状态。

9. 常见错误

  • 用栈或递归代替队列，算法就变成 DFS；
  • 出队时才标记，导致重复入队；
  • 忘记初始化不可达距离为无穷；
  • 有不同边权时仍把 BFS 当最短路；
  • 只从顶点 1 启动，却声称遍历了非连通图。

评论