图搜索有两个不同的问题:哪些顶点可以到达?到达它们最少要经过多少条边?在无权图中,广度优先搜索(BFS)可以同时回答这两个问题。队列使较早的距离层先被处理,父指针则记录一条证明答案的路径。
一个小操作的时机很重要。如果顶点只在离开队列时才被标记,多个邻居可能早已把它重复入队。改为在入队时标记,可以使每个顶点只入队一次,也固定了首次发现它的父顶点。我们会证明第一次发现就已经给出最短路径,而不是只相信一次追踪的结果。
定义距离和数据结构
定义 13.1.1
(最短路径距离)
设 为有限有向图,顶点为 ,其中 ;选定起点 。每条列出的有向边算一步。若存在从 到 的有向路径,距离 是其最少边数;否则设 。起点通过零长路径到达自身,距离为零。
无向边可以在两个方向各存一个邻接项。允许自环及重复的邻接项,但它们不会造出更短的路径。下面用 表示列出的有向邻接项的个数,重复项也计算在内。
定义 13.1.2
(队列和标签)
维持先进先出队列、距离数组与父顶点数组。距离中的 None 表示尚未发现。起初起点的距离为 0 并已入队;其他距离及所有父顶点均为 None。
取出顶点 时,检查它列出的每个出邻居 。若 distance[v] 是 None,就设为 distance[u] + 1,设 parent[v] = u,并立即把 入队。若 已被发现,保持它的标签和父顶点不变。距离数组同时充当发现标记。
算法结束后,距离数组中的 None 表示不可到达;执行期间它只表示尚未发现,之后的队列项仍可能到达该顶点。
常见错误
(太早把 None 当作不可到达)
在六顶点的例子中取出 1 之后,distance[4] 仍是 None,但 4 可以从 0 到达。搜索进行期间,None 只表示还没有已取出的顶点发现过它;只有队列清空之后,它才表示不可到达。
追踪两条可能的路径
例题 13.1.3
(队列逐层显示距离)
下面的邻接表按列出的顺序读取,起点为 0:
| 顶点 | 出邻居 |
|---|---|
| 0 | 1, 2 |
| 1 | 3 |
| 2 | 3, 4 |
| 3 | 4 |
| 4 | 无 |
| 5 | 无 |
队列起初是 [0]。取出 0,发现 1 和 2,得到 [1, 2]。取出 1,发现 3,得到 [2, 3]。取出 2,先看到 3 已被发现,再发现 4,得到 [3, 4]。余下的取出操作没有新增顶点。
最后的距离为 [0, 1, 1, 2, 2, None]。一组父顶点是 [None, 0, 0, 1, 2, None]:从 4 沿父指针得到 4、2、0,倒过来就是最短路径 。路线 也是有向路径,但用了三条边。起点 0 无法到达顶点 5。
如果 0 的邻接表改成 [2, 1],顶点 3 可能改以 2 为父顶点。BFS 可以选到不同的最短路径证据,但距离不会因此改变。
例题 13.1.4
(自环与重复项只影响 m)
取邻接表 0: [1, 1, 0]、1: [2, 0]、2: [1],起点为 0。取出 0 时发现 1,距离 1、父顶点 0;重复的 1 和自环 0 都碰到已有标签的顶点,不产生任何改变。取出 1 时发现 2,距离 2、父顶点 1,项 0 被跳过。取出 2 时检查 1,它已有标签。结果是距离 [0, 1, 2]、父顶点 [None, 0, 1]。共检查了六个邻接项,所以 ,但每个顶点只入队一次。
为什么第一次发现就已经最短
定理 13.1.5
(BFS 计算最短距离)
设 为有限有向图, 为其中一个顶点。队列清空后,对每个可从 到达的顶点 ,distance[v] 等于 ;不可到达的顶点,distance[v] 恰好是 None;而从可到达的 沿父指针回溯,得到一条从 出发、长度恰为该距离的路径。
证明
(先进先出保持非递减的距离层)
起点以标签 0 入队。每当取出标签为 的顶点,所有新入队的邻居的标签都是 。队列中的标签非递减:起初只有一个零;取出队首不会破坏次序,而新标签不小于队中现有的标签。更精确地说,处理第 层时,队列只含尚未处理的标签 ,其后可能跟着标签 。取出一个 并在队尾加入 之后,这个性质仍然成立。
每个已发现的顶点都确实有一条长度等于其标签的、从起点出发的路径:起点用空路径;每次发现只是在父顶点的证据路径后面加一条边。因此标签不可能小于真正的最短距离。
反过来,设可到达的顶点 的最短距离是 ,选一条最短路径 。对 归纳。起点的标签是零。若 的标签至多为 ,它最终会被取出:顶点有限,每个顶点最多入队一次。取出它时, 要么已有标签,要么借助边 得到至多为 的标签。
若它更早已有标签,先进先出的层次顺序说明,发现它的顶点的标签不大于取出 时的标签。因此它的标签也至多为 。于是 的标签至多为 ;结合已有实际路径所给出的反向不等式,标签恰好等于 。
队列清空后,上述论证说明每个可到达的顶点都已被发现;不可到达的顶点不可能被发现,因为每次发现都附带一条从起点出发的实际路径。因此余下的 None 恰好是不可到达的顶点。
证明透视
先进先出用在哪一步
整个证明只有一步需要队列的规则: 在 被取出之前就已有标签的情形。那时发现它的顶点更早被取出,而先进先出使取出时的标签非递减,所以该顶点的标签至多等于 的标签, 因而得到至多为 的标签。其余部分,即证据路径和有限终止,与顺序无关。如果用栈代替队列,正是这一步失效,见下面的例子。
也可以用取出顺序作一个较短的证明:若新发现的顶点另有严格更短的路径,该路径上紧接在它之前的顶点应在较早的一层先被取出,从而更早发现它。两种证明都依赖 FIFO 顺序,而不只依赖最终是否遍历了所有顶点。
反例模式
用栈并在发现时标记,距离会出错
取有向边 、、、、,邻接表按此顺序,起点为 0,并把队列换成栈,仍然在入栈时标记顶点。取出 0 时压入标签同为 1 的 1 和 2;位于栈顶的 2 最先被取出,并压入标签为 2 的 3;取出 3 时压入标签为 3 的 4。顶点 1 最后才被取出,发现 4 已有标签。算法报告顶点 4 的距离是 3,但路径 的长度只有 2。每个顶点仍然只被发现一次,可见“发现时标记”本身不足以给出最短路径,真正起作用的是先进先出的顺序。
边界清楚的实现
输入是可按索引读取的邻接序列,每个邻居都是整数顶点。下面的版本检查所有邻居的索引,包括起点无法到达的分量,并且不修改输入。使用 deque 可以从队首取出元素而不必移动整个数组。
from collections import deque
def breadth_first_search(graph, source):
n = len(graph)
if not 0 <= source < n:
raise ValueError("source outside the vertex range")
for neighbors in graph:
for vertex in neighbors:
if not 0 <= vertex < n:
raise ValueError("neighbor outside the vertex range")
distance = [None] * n
parent = [None] * n
distance[source] = 0
queue = deque([source])
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 shortest_path(distance, parent, source, target):
if not 0 <= source < len(distance) or not 0 <= target < len(distance):
raise ValueError("endpoint outside the vertex range")
if distance[target] is None:
return None
path = []
v = target
while v != source:
path.append(v)
v = parent[v]
path.append(source)
path.reverse()
return path
shortest_path 假设收到的是同一个起点执行 breadth_first_search 所返回的数组。目标就是起点时返回 [source]:零条边的路径不需要父顶点。不可到达的目标返回 None。对已发现的非起点顶点,每个父顶点的距离恰好少一,所以回溯有限步后到达起点。把收集到的顶点倒过来,便得到长度恰好等于标签的正向路径。
概念视角结构
输出是一棵分层的树
记 为各距离层。从可到达顶点 出发的每条有向边 都满足 ,因此它要么留在同一层,要么退回更早的层,要么恰好前进一层。父指针对应的边就是用来发现顶点的前进边:每个可到达的非起点顶点恰有一条,它们构成以 为根的树,边数等于各层顶点总数减一。在六顶点例子中,各层为 ,树边为 、、、;边 留在第 2 层之内。
例题 13.1.6
(重建路径,包括起点本身)
沿用六顶点例子的数组:距离 [0, 1, 1, 2, 2, None],父顶点 [None, 0, 0, 1, 2, None]。目标为 3 时,循环收集 3 与 1,再加入起点 0,倒过来得到 [0, 1, 3],共两条边,等于 distance[3]。目标为 0 时,循环体一次也不执行,结果是 [0]。目标为 5 时距离为 None,函数返回 None。只有一个顶点而没有边的图 graph = [[]],搜索返回距离 [0] 与父顶点 [None]。
输入约定假设顶点为整数、邻接序列格式正确;边界检查不会验证所有可能格式错误的 Python 对象。实际产品的接口可以按自己的约定增加更严格的类型和错误处理。
计算工作量,也避免误用于加权图
命题 13.1.7
(BFS 的时间与空间)
以上述实现,搜索需要 时间及 个额外单元,其中 表示列出的有向邻接项的个数,重复项也计算在内。重建含 条边的路径需要 时间。
证明
(顶点数与邻接项数)
初始化及验证扫描需要 时间。每个顶点最多入队及取出一次,每个已到达顶点的出邻接项最多检查一次,额外时间至多为 。距离、父顶点与队列使用 额外空间,不包括输入图。重建含 条边的路径需要 时间及输出空间。
反例模式
边数最少未必权重最小
假设加权有向图有 ,权重 10,另有 与 ,权重各为 1。BFS 把每条边当作一步,选择只有一条边的直接路径,权重却是 10;两条边的路径总权重是 2。上面的 BFS 证明优化的是边数,而不是任意权重的总和;即使允许零权重的边,一般的 BFS 也不是通用的加权最短路径算法。
BFS 只是一种搜索顺序,不能代替对目标的定义。若边的权重要紧,应选择符合其假设的算法,并证明相应的不变量。对无权问题,队列顺序及首次发现的父顶点共同给出最优距离和可检查的证据。
练习与解答
快速检查
(1. 在六顶点的例子中,取出 1 之后队列是什么?给出到 4 的一条最短路径。)
解答 · 解答 1
取出 1 之后队列是 [2, 3]。其后 2 发现 4,沿父顶点得到最短路径 ,长度为 2。在 2 被取出之前 4 尚未被发现;当时的 None 并不代表它不可到达。
快速检查
(2. 起点自身的距离与路径是什么?例子中的顶点 5 又返回什么?)
解答 · 解答 2
起点的距离为 0,路径是 [0],即零长路径。顶点 5 的距离为 None,搜索完成后可知起点无法到达它,因此 shortest_path 返回 None。
快速检查
(3. 若有 、、、,为什么只在取出 3 时才标记可能产生额外的队列项?)
解答 · 解答 3
3 到达队首之前,1 和 2 都可能先检查它。如果入队时没有记录发现,两者都可能把它入队。第一次由 1 入队时立即标记,就使 2 之后看到它已被发现而跳过,只保留一个队列项和一个首次父顶点。不同的邻接顺序仍然可能选到另一个同样短的父顶点。
快速检查
(4. 为什么搜索是 而不是 ?这里的 m 计算什么?)
解答 · 解答 4
数组只初始化一次,每个顶点最多入队一次。扫描被取出顶点的邻接表时,每个列出的出邻接项最多检查一次;事前的验证也只扫描一次,所以总工作量是 。 包括重复的有向邻接项;若无向边在两个方向各存一次,就贡献两项。