查看“︁广度优先搜索”︁的源代码

'''广度优先搜索'''（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 也有三条边，所以最短路径不一定唯一。

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

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

{| class="wikitable"
! 出队 !! 新发现 !! 出队后的队列
|-
| S || A、B || A，B
|-
| A || C、D || B，C，D
|-
| B || 无 || C，D
|-
| C || E || D，E
|-
| D || 无 || E
|}

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

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

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

<math-experiment type="algorithm" demo="breadth-first-search" />

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

<div class="math-code-example">
<div class="math-code-language">Python 3</div>
<pre class="math-code-source" data-language="python">
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
</pre>
</div>

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

== 参考资料 ==
* [https://github.com/TheAlgorithms/Python/blob/c27e95123cb7e2fef5b15e64b5e800201cc7665c/graphs/breadth_first_search.py TheAlgorithms/Python：breadth_first_search.py]；[https://github.com/TheAlgorithms/Python/blob/c27e95123cb7e2fef5b15e64b5e800201cc7665c/graphs/breadth_first_search_shortest_path.py 同仓库的最少边数路径实现]。本站用独立案例与代码统一讲解。
* [https://algs4.cs.princeton.edu/41graph/ Sedgewick、Wayne，Undirected Graphs]：BFS 的最少边数路径与邻接表分析。
* 先修：[[图论]]、[[算法与复杂度]]；后续：[[深度优先搜索]]、[[最短路径]]。
[[分类:算法]]