广度优先搜索

广度优先搜索（breadth-first search，BFS）从一个起点出发，先访问相距一条边的顶点，再访问相距两条边的顶点，依次向外扩展。这里的“距离”是经过的边数，并不自动等于道路费用或几何长度。输入是一张有限图及起点；输出可以是每个顶点的最少边数和一条达到该边数的路径。

按边数展开的图

考虑无向图，顶点为 S、A、B、C、D、E、F，边为 SA、SB、AC、AD、BD、CE、DE，F 没有边。邻接点按字母顺序读取。图中 S 在第 0 层，A、B 在第 1 层，C、D 在第 2 层，E 在第 3 层；F 从 S 不可达。由前驱线可读出 S→A→C→E，一共三条边。S→A→D→E 也有三条边，所以最短路径不一定唯一。

无向图从S分出A和B，A连C和D，B连D，C和D都连E，F孤立；按最少边数分为零到三层，F不可达 — 彩色线是按字母顺序搜索时首次发现顶点所留下的前驱边；虚线也属于原图，却不是这次选中的前驱。

队列记录了下一层

起初把 S 标为已发现并入队。每次取出队首顶点，把尚未发现的邻点按顺序放到队尾；入队时就标记，免得 D 从 A 与 B 被重复放入。前五次出队后的队列如下；第六次取出 E 后队列为空。

出队	新发现	出队后的队列
S	A、B	A，B
A	C、D	B，C，D
B	无	C，D
C	E	D，E
D	无	E

发现邻点时，记录它的距离为当前顶点距离加 1，并把当前顶点记为前驱。故 $d (S) = 0$ ， $d (A) = d (B) = 1$ ， $d (C) = d (D) = 2$ ， $d (E) = 3$ ；F 的距离保持“不可达”。沿 E 的前驱 C、A、S 反向回溯，就得到图示路线。

层次与最短边数

队列先进先出。处理距离为 $k$ 的顶点时，新加入的邻点距离为 $k + 1$ ，排在尚未处理的第 $k$ 层顶点之后。因此出队距离不会下降。假设顶点 $v$ 首次从第 $k$ 层发现，得到长度 $k + 1$ 的路线。若存在更短路线，其倒数第二个顶点应在第 $k - 1$ 层或更早，早已出队并发现 $v$ ，与“首次发现”矛盾。记录的距离因而是最少边数。

给图再加一条 SE，E 的最少边数立刻变成 1。若 SE 的费用是 10，而 SA、AC、CE 的费用各是 1，那么一条边的路线费用为 10，三条边的路线费用为 3。BFS 仍正确计算边数，却不解决这个带权费用问题；非负费用的最小路线应查看最短路径中的 Dijkstra 方法。

广度优先搜索的队列

按队列顺序扩展顶点，查看层数和首次发现的前驱。

静态配图与完整推导见本节正文；交互演示需浏览器启用 JavaScript。

Python 实现

邻接表列出每个顶点，包括没有边的 F；每条无向边要在两端各写一次。parent 只为已经发现的顶点记录前驱，route 用它还原一条最短路线。

Python 3

from collections import deque


def bfs(graph, start):
    if start not in graph:
        raise KeyError(start)
    distance = {vertex: None for vertex in graph}
    parent = {start: None}
    distance[start] = 0
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if distance[v] is None:
                distance[v] = distance[u] + 1
                parent[v] = u
                queue.append(v)
    return distance, parent


def route(parent, target):
    if target not in parent:
        return None
    result = []
    while target is not None:
        result.append(target)
        target = parent[target]
    return list(reversed(result))


if __name__ == "__main__":
    graph = {
        "S": ["A", "B"], "A": ["C", "D", "S"],
        "B": ["D", "S"], "C": ["A", "E"],
        "D": ["A", "B", "E"], "E": ["C", "D"], "F": [],
    }
    distance, parent = bfs(graph, "S")
    assert distance == {
        "S": 0, "A": 1, "B": 1, "C": 2,
        "D": 2, "E": 3, "F": None,
    }
    assert route(parent, "E") == ["S", "A", "C", "E"]
    assert route(parent, "F") is None

扫描成本与边界

以邻接表表示图时，每个顶点最多入队一次，每条无向边从两端各检查一次，时间为 $O (V + E)$ ；距离、前驱与队列合计用 $O (V)$ 额外空间，其中 $V$ 是顶点数、 $E$ 是边数。邻接矩阵若逐行寻找邻点，时间通常变为 $O (V^{2})$ 。代码约定每个邻点都已列为字典键，且邻接表顺序固定；改变邻接顺序可能换一条同长度路线，却不会改变最少边数。与沿一条路走到底的深度优先搜索相比，BFS 保留整层待访问顶点。

参考资料

TheAlgorithms/Python：breadth_first_search.py；同仓库的最少边数路径实现。本站用独立案例与代码统一讲解。
Sedgewick、Wayne，Undirected Graphs：BFS 的最少边数路径与邻接表分析。
先修：图论、算法与复杂度；后续：深度优先搜索、最短路径。