广度优先搜索（BFS）详解：原理、代码与复杂度

BFS 解决什么问题

许多问题本质上都是图：网页与链接、社交网络中的好友、棋盘上的格子、谜题的各种状态。BFS 回答这类图上的两个常见问题：从起点出发能到达哪些节点？到达每个节点最少需要几步？

由于 BFS 按距离递增的“圈层”向外探索，第一次到达某个节点时，走的一定是边数最少的路径。因此当所有边的代价相同时，BFS 是求最短路径的标准算法。

用大白话讲思路

1. 把起点放入队列，并标记为已访问。
2. 取出队首的节点。
3. 对每个尚未访问的邻居，标记为已访问，并加入队尾。
4. 重复第 2、3 步，直到队列为空。

应当在节点入队时就标记为已访问，而不是出队时。否则同一个节点在被处理之前可能被重复入队很多次。

逐步演示一个例子

考虑这个无向图：A–B、A–C、B–D、C–D、C–E、D–F。从 A 出发，邻居按字母顺序访问。

访问顺序为 A、B、C、D、E、F。D 既能从 B 到达，也能从 C 到达，但只会被发现一次（由 B 发现），因为那时它已被标记为已访问。

Python 实现

队列用 collections.deque：popleft() 是 O(1)，而 list.pop(0) 是 O(n)。图用字典表示，每个节点映射到邻居列表（邻接表）。

from collections import deque
def bfs(graph, start):
    """Return the distance (number of edges) from start to each reachable node."""
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:          # not visited yet
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(bfs(graph, "A"))  # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}

这里的 dist 字典一物两用：既是已访问集合，又保存了结果。若要还原具体路径，还需记录每个节点的父节点，再从目标节点往回走。

def shortest_path(graph, start, goal):
    parent = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]
        for nxt in graph[node]:
            if nxt not in parent:
                parent[nxt] = node
                queue.append(nxt)
    return None  # goal not reachable
print(shortest_path(graph, "A", "F"))  # ['A', 'B', 'D', 'F']

时间与空间复杂度

V 是顶点（节点）数，E 是边数。如果用邻接矩阵代替邻接表，时间会变成 O(V²)，因为查找一个节点的所有邻居需要 O(V)。

变体与常见错误

• 网格 BFS：把每个格子看作节点，上下左右（或八个方向）的相邻格子看作边。加入格子前先检查边界和障碍。
• 多源 BFS：把多个起点以距离 0 一起放入队列，可求到最近起点的距离，例如迷宫中离你最近的出口。
• 0-1 BFS：当边权只有 0 或 1 时，用双端队列，把权为 0 的邻居放到队首，可在 O(V + E) 内求出最短路径。
• 双向 BFS：同时从起点和终点出发搜索，两个搜索前沿相遇时停止，通常能少探索很多节点。
• 按层处理：每一轮开始时记录 len(queue)，恰好弹出这么多节点，就能一次处理一整层。

何时使用 BFS 及实际应用

• 面试题：迷宫或网格中的最短路径、单词接龙、腐烂的橘子（多源 BFS）、二叉树层序遍历、骑士的最少走法。
• 网络：查找 k 跳以内的所有设备、点对点网络中的广播、社交图中距离为 2 的“可能认识的人”。
• 网络爬虫：按与种子页面的链接距离依次访问页面。
• 垃圾回收器（例如 Cheney 复制式回收器）以及需要最少步数的谜题求解器。