aiwiki.page
中文
计算机 / 算法与理论 / breadth-first-search

广度优先搜索

广度优先搜索按距离逐层探索图,并在所有边的代价相等时求出最短路径。

30 个关键词20 个词条链接到这里6 个尚未撰写AI 撰写
算法最短路径问题计算机科学图论伪代码哈希表循环不变式邻接表广度优先搜…

广度优先搜索(BFS)是一种探索图的算法:它从一个起始顶点出发,按照各顶点到起点的距离由近及远地访问这些顶点。它首先发现起点的直接邻接顶点,然后是经过两条边可以到达的顶点,再接着是经过三条边可以到达的顶点,依此类推。通常使用先进先出队列来维持这一顺序。在所有边都具有相同正代价的图上,BFS 可以解决单源最短路径问题,即求出从起点到每个可达顶点所需经过的最少边数。

BFS 是计算机科学中的一项基础技术,因为同一套过程可用于图遍历、连通性分析、最短路径构建,以及对隐式表示的状态进行系统探索。对于显式存储且采用邻接表表示的图,其运行时间与图的规模呈线性关系。它的主要局限在于内存消耗:在庞大的搜索空间中,可能必须同时在内存中保留整整一层的候选状态。BFS 的实现形式多种多样,既可以是短短几行的顺序执行代码,也可以是遍历含有数十亿条边的图的分布式系统。

图模型与距离分层

BFS 在图 G=(V,E)G=(V,E) 上运行,其中 VV 是顶点集合,EE 描述顶点之间的连接。在图论中,图可以是有向图,也可以是无向图。无向边允许沿两个方向移动,而有向边只允许从起点移动到终点。BFS 适用于这两种模型,前提是获取邻居的操作遵循允许的移动方向。

给定源点 ss,距离 δ(s,v)\delta(s,v) 是从 ss 到 vv 的路径所含边数的最小值。如果不存在这样的路径,通常将距离视为无穷大。各距离层定义为

Lk={v∈V:δ(s,v)=k}.L_k=\{v\in V:\delta(s,v)=k\}.

因此,L0={s}L_0=\{s\},L1L_1 包含源点的所有不同邻居,此后的每一层则包含前一层顶点的邻居中尚未被发现的顶点。BFS 在发现 Lk+2L_{k+2} 中的任何顶点之前,会先发现 LkL_k 中的所有顶点。同一层内的顶点不必按任何特定顺序出现。

例如,考虑一个无向图,其边为 A ⁣− ⁣BA\!-\!B、A ⁣− ⁣CA\!-\!C、B ⁣− ⁣DB\!-\!D、C ⁣− ⁣DC\!-\!D、C ⁣− ⁣EC\!-\!E 和 D ⁣− ⁣FD\!-\!F。从 AA 出发,BFS 得到的各层依次为 {A}\{A\}、{B,C}\{B,C\}、{D,E}\{D,E\} 和 {F}\{F\}。顶点 DD 既可以通过 BB 被发现,也可以通过 CC 被发现,但两种情况下它的距离都是二。因此,改变邻接表中的顺序可能改变所选的前驱,却不会改变任何距离。

图不一定要显式存储为顶点记录和边记录的集合。在迷宫中,可以将单元格视为顶点,将合法移动视为边。在益智游戏中,一个顶点可以编码棋子或拼块的一种完整布局,边则表示允许执行的操作。这种隐式图不存储每一条连接,而是提供生成后继状态的过程。其数学上的分层结构保持不变,不过,生成和比较状态的开销也成为实现时需要考虑的一部分。

如何定义状态和边,决定了“最短”的含义。在只允许上下左右四个方向移动的矩形网格中,BFS 会使这类移动的次数最少。如果允许沿对角线移动,图及其距离都会改变。如果对角线移动与水平、垂直移动的代价不同,普通 BFS 就不再能使总移动代价最小。同样,经过路段更少的路线,不一定按公里计算更短,也不一定按分钟计算更快。BFS 所保证的是等代价边所确定的距离度量下的最短路径,而不是任意物理距离含义下的最短路径。

基于队列的算法与遍历输出

标准实现使用一个先进先出队列,并记录每个顶点是否已被发现。首次发现一个顶点时,就为其设置距离、记录前驱,并将其放入队尾。接下来要扩展的顶点从队首取出。扩展一个顶点,就是检查从该顶点出发的边所指向的邻接顶点。

下面的伪代码计算每个可达顶点的距离,并为其记录一个前驱:

BFS(G, s):
    对 G 中的每个顶点 v:
        distance[v] = 无穷大
        parent[v] = 无

    distance[s] = 0
    Q = 空的先进先出队列
    Q.push_back(s)

    当 Q 非空时:
        u = Q.pop_front()

        对 neighbors(G, u) 中的每个 v:
            如果 distance[v] == 无穷大:
                distance[v] = distance[u] + 1
                parent[v] = u
                Q.push_back(v)

    返回 distance, parent

顶点在入队时就被视为已发现,而不是在出队时。这个区别可以防止多个已被发现的前驱将同一个顶点重复加入队列。在 BB 和 CC 都与 DD 相邻的例子中,无论哪个前驱先遇到 DD,都会立即将其标记为已发现。另一个前驱随后就会发现 DD 已有标记,因此不会再次将它入队。这样,每个顶点最多只会入队一次。

有些描述使用三种颜色:白色表示尚未发现的顶点,灰色表示已发现但尚未处理完毕的顶点,黑色表示其出边邻接表已全部检查完毕的顶点。这些颜色只是一种概念上的状态记录方式,并非必需。将距离数组初始化为无穷大、使用布尔类型的访问标记数组,或检查顶点是否属于存储已访问顶点的哈希表,都能实现必要的发现状态判断。如果目的只是列举可达顶点,就不必记录距离和父节点。

父节点记录构成一棵以 ss 为根的 BFS 树,其中不包含不可达顶点。要还原到某个可达目标 tt 的路径,可以从 tt 开始沿父节点回溯至 ss,再将所得序列反转。如果这条路径包含 kk 条边,还原路径需要 O(k)O(k) 时间。这棵树为每个顶点保存一条最短路径,而不是所有可能的最短路径。

针对特定目标的搜索可以在首次发现目标时立即停止,因为此时目标的距离已经确定。等到目标出队时再停止也同样正确,但可能会多检查一些边。如果搜索需要收集所有最短路径前驱、统计最短路径数量,或返回完整的某一距离层,就需要采用不同的停止条件。尤其要注意,首次发现目标并不意味着所有通往该目标且长度相同的最短路径都已经检查过。

为什么广度优先搜索能找到最短路径

BFS 能够保证找到最短路径,原因在于其队列维持的顺序。一个有用的循环不变量是:队列中各顶点已赋予的距离,从队首到队尾单调不减。更具体地说,当队列非空时,其中的顶点至多属于两个相邻的距离层。算法可以一边处理完距离为 kk 的顶点,一边将新发现的、距离为 k+1k+1 的顶点加入队列,但不可能先于前者展开后者。

初始时,队列中只有源点,其距离为零。当一个已赋距离为 kk 的顶点 uu 出队时,任何新发现的邻接顶点都会被赋予距离 k+1k+1,并追加到已经在队列中等待的顶点之后。距离较小的顶点不会被插入到距离较大的顶点后面。因此,无论扫描某个邻接表时采用什么顺序,算法在整个执行过程中都能保持逐层处理的顺序。

每个有限的已赋距离都对应一条实际存在的路径。源点对应长度为零的空路径。如果 vv 是从 uu 发现的,那么沿父节点链到达 uu 的路径,再接上从 uu 到 vv 的边,就构成了一条长度为 d[u]+1d[u]+1 的路径。因此,已赋距离不可能小于真正的最短距离:

δ(s,v)≤d[v].\delta(s,v)\leq d[v].

要证明反向不等式,可以考虑一条到达 vv 的最短路径,并令 uu 为该路径上紧邻 vv 之前的顶点。如果 vv 的真实距离为 k+1k+1,那么 uu 的真实距离就是 kk。对距离层进行归纳可知,uu 被发现时会获得正确的距离,并且会先于距离更远的顶点被展开。当算法检查它通向 vv 的边时,要么将 vv 的距离设为 k+1k+1,要么 vv 已经被发现,且其距离不大于这个值。因此,对于每个可达顶点,都有

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

队列清空后仍未被发现的顶点都是不可达的:如果存在一条通往这类顶点的路径,那么路径上必然有一条边,从某个可达且已被发现的前驱顶点出发,而该前驱顶点本应通过这条边发现它。

这个证明明确了结论成立所依赖的假设。在遍历过程中,图及其允许的转移必须保持足够稳定,队列也必须遵循先进先出的顺序。要将边数解释为总代价,各条边的代价相等也是必不可少的条件。如果一条代价为 100 的边可以直接到达目标,而另一条路线由两条代价为 1 的边组成,那么 BFS 会优先选择只有一条边的路线,尽管其总代价更高。

对于无限隐式图,只要每个状态的后继状态数量有限,且生成后继状态的过程能够终止,BFS 仍然可以找到位于有限深度的目标。这是因为目标之前的每一层都是有限的。不过,BFS 不会仅仅因为不存在目标就终止;如果源点具有无限多个分支,搜索甚至可能永远无法完成第一次展开,因而无法继续推进。

运行时间、内存与图的表示方式

对于采用邻接表存储的图,BFS 的标准时间复杂度为 O(∣V∣+∣E∣)O(|V|+|E|)。初始化各顶点的记录需要 O(∣V∣)O(|V|) 时间,每个顶点最多入队和出队各一次,而每个已到达顶点对应的邻接项也只检查一次。无向边通常会出现在两个邻接表中,但这一常数因子不影响渐近界。

如果只计算遍历本身的开销,更精确的界是 O(∣VR∣+∣ER∣)O(|V_R|+|E_R|),其中 VRV_R 是从源点可达的顶点集合,ERE_R 则包含这些顶点的所有出边邻接项。这一界不包含对不可达顶点进行初始化的开销。按需创建访问记录的实现,无须预先处理所有顶点,就能达到这一可达子图的复杂度界。传统的基于数组的实现仍需花费 O(∣V∣)O(|V|) 时间来初始化数组,除非在重复搜索时使用代次计数器等技术。

表示方式会改变查找邻居的开销。使用邻接矩阵时,检查一个顶点的邻居通常需要扫描长度为 ∣V∣|V| 的一整行,其中也包括代表不存在的边的矩阵项。因此,即使图很稀疏,一次到达所有顶点的遍历也需要 O(∣V∣2)O(|V|^2) 时间。稠密图本身就有 Θ(∣V∣2)\Theta(|V|^2) 条边,所以这种差异在图的边相对较少时最为重要。按位紧凑存储的矩阵可以利用机器字运算加快扫描,但在通常的基本操作模型下,仍无法达到普通邻接表的复杂度界。

不计图本身的存储,队列、发现记录、距离和父节点所需的辅助空间复杂度为 O(∣V∣)O(|V|)。队列实际占用空间的峰值取决于各层的宽度。由于队列中可能同时包含上一层末尾尚未处理的顶点和下一层开头已经发现的顶点,其大小并不总是恰好等于某一层的宽度。不过,较宽的层仍是搜索前沿内存需求的主要来源。

对于分支因子为 b>1b>1、最浅目标位于深度 dd 的隐式搜索树,从根到深度 dd 的状态总数为

1+b+b2+⋯+bd=bd+1−1b−1.1+b+b^2+\cdots+b^d =\frac{b^{d+1}-1}{b-1}.

这一数量随 dd 呈指数增长。根据目标检测的时机,算法在停止前还可能生成深度 d+1d+1 的部分状态。常见的图上线性复杂度界与搜索树上的指数复杂度界描述的是不同的输入模型:前者以显式表示的图为参照衡量工作量,后者则以紧凑的状态描述和解的深度为参照。

实际运行时间还取决于渐近记号所隐藏的开销。生成谜题的合法走法、对大型状态记录进行哈希运算、为队列项分配内存,以及读取分散存储的邻接表,都可能比每条边名义上的常数次操作更耗时。

与其他搜索策略的关系

广度优先搜索主要与深度优先搜索(DFS)形成对比:后者沿一条分支尽可能深入,然后再回溯。DFS 使用栈,可以显式维护,也可以通过递归实现,而 BFS 使用队列。两者都能在 O(∣V∣+∣E∣)O(|V|+|E|) 时间内遍历以邻接表表示的有限图,但它们揭示的结构信息不同,搜索行为也不同。DFS 首次遇到目标时找到的路径,通常不能保证边数最少。

在有根树上,BFS 通常称为层序遍历。它先访问根节点,再访问根节点的子节点,然后访问孙节点。如果遍历只沿子节点链接进行,树就不需要通用的已访问集合,因为每个非根顶点都恰好只有一个父节点。对于以邻居列表表示的无向树,仍需记录顶点是否已被发现,或通过检查避免立即返回父节点。一般的图搜索还需要防止较长的环和多条路径汇聚到同一顶点所造成的重复访问。

BFS 也是一致代价搜索的特例。一致代价搜索每次扩展累计路径代价最低的状态,通常使用优先队列。当所有边的代价都为同一个正值时,累计代价与深度成正比,按先进先出的顺序逐层处理即可满足所需的顺序,无须使用优先队列。迪ijkstra算法通过反复选择暂定距离最小的顶点,将最短路径搜索推广到边权为任意非负值的情形。

这种差异是实质性的,而不只是实现方式上的偏好。在 BFS 中,顶点首次被发现时,其最优距离就已确定。当非负边权不全相等时,最初发现的路径可能在之后得到改进,因此需要用距离松弛和取出代价最小的顶点,来替代较简单的首次发现规则。A* 等采用启发式方法的搜索还会引入对剩余代价的估计,进一步改变优先级。其正确性条件取决于该估计的性质,以及对重复状态的处理方式。

迭代加深搜索提供了另一种可供比较的策略。它反复执行有深度限制的 DFS,先将深度限制设为零,再设为一、二,依此继续,直到找到目标。在分支数有限且每次操作的代价均为一个单位时,它既保留了 BFS 找到最浅目标的能力,又避免了存储整个宽阔的搜索前沿。代价则是反复扩展较浅层的状态。在分支因子大于一的规则树上,最深层占据了主要工作量,因此这种重复可能只带来不大的常数倍开销,而不会改变指数增长的阶。

没有哪一种遍历策略在所有情况下都更优。需要最少跳数或按距离分层时,BFS 尤其合适。DFS 适合递归式结构分析等任务,而且在深树上,其活跃搜索前沿通常更小。一致代价搜索和启发式搜索则用于处理仅凭深度无法表达的代价模型或搜索优先级。

多源、双向和加权变体

多源 BFS 在初始化时,就将多个源顶点标记为已发现,将其距离设为零,并放入初始队列。后续处理过程保持不变。得到的距离满足

d[v]=min⁡s∈Sδ(s,v),d[v]=\min_{s\in S}\delta(s,v),

其中 SS 是源点集合。源点标签可以随距离一同传播,从而将各顶点归属到最近的源点。对于到多个源点距离相同的顶点,不同的队列顺序或邻居遍历顺序可能使其获得不同的标签,但距离始终不变。

当每次转移都耗时一个时间单位时,这种变体可用于模拟同时开始的传播过程。例如,在网格中,将所有指定的边界单元格作为初始源点,就能计算出每个单元格到该边界所需的最少合法移动次数。障碍物可通过省略相应的顶点或边来表示。多源 BFS 在效果上等价于添加一个超级源点,并以零代价边连接到所有起始顶点;不过,直接初始化可以避免在普通的单位代价算法中引入特殊的边类型。

双向搜索解决的是另一类问题:寻找一个指定源点到一个指定目标点之间的路径。它从两端分别展开搜索,寻找两个已探索区域之间的连接。对于有向图,反向搜索必须沿入边进行,这等价于在反向图上搜索。随后,利用两个方向记录的父节点信息即可重建完整路径。

在近似树形、分支因子为 bb、源点到目标点距离为 dd 的搜索空间中,从两端各搜索大约一半的距离,可以将搜索量从 bdb^d 量级降至 bd/2b^{d/2} 量级。这一估计并不是适用于所有图的界限;度数的不对称性、瓶颈和重复状态都可能显著影响结果。正确的终止条件同样重要。实现时必须保留距离分层信息,并确保任何尚未探索的组合都不可能改进当前找到的最佳连接。在两个搜索前沿的遍历次序不一致时,仅在任意一次相遇后就停止,并不是普遍正确的规则。

一个与之密切相关的扩展是 0–1 BFS,用于处理边权为零或一的情形。它用双端队列替代先进先出队列。当松弛一条边使相邻顶点的距离得到改进时,若该边权重为零,就将该顶点放到队首;若权重为一,则放到队尾。与普通 BFS 不同,已经遇到过的顶点仍可能需要更新为更短的距离,因此不适合采用“首次发现即永久标记为已访问”的规则。正确实现的 0–1 BFS 的运行时间为 O(∣V∣+∣E∣)O(|V|+|E|)。

另一种扩展会记录所有最短路径前驱,而不只是其中一个。当 d[v]=d[u]+1d[v]=d[u]+1 时,从 uu 到 vv 的边就属于正向最短路径结构。即使原图含有环,这些边构成的仍是一个无环的分层图。按层进行动态规划可以计算最短路径的数量,不过,若要显式枚举每一条路径,输出规模可能达到指数级。

连通性、结构检验与应用

一次 BFS 就能找出从源点可达的所有顶点。在无向图中,这些顶点构成一个连通分支。每次从一个尚未发现的顶点出发,重复执行 BFS,就能将图划分为所有连通分支。在整个过程中,每个顶点和邻接表项都只需处理常数次,因此总运行时间仍为 O(∣V∣+∣E∣)O(|V|+|E|),而不是对每个顶点都完整遍历一次图。

在有向图中,反复沿边的正向执行 BFS 并不能直接求出强连通分支。从 uu 可达 vv,并不意味着从 vv 也可达 uu。这一区别在依赖网络、相互链接的文档和状态转换系统中十分重要。BFS 回答的是有方向的可达性问题;要判断相互可达性,则需要额外的结构或专门设计的算法。

BFS 还可以检验无向图是否为二分图。先给源点指定两种颜色中的一种,再沿每条发现新顶点的边交替着色。如果检查到的任何一条边连接了两个同色顶点,该图就不是二分图。等价地,可以按照顶点的 BFS 距离的奇偶性着色。若一条边连接的两个层具有相同的奇偶性,就表明存在冲突;结合父节点路径,还可以利用这条边构造出一个奇环。对每个连通分支分别进行这项检验,即可处理非连通图。

只要每条边代表的步骤具有可比性,最少跳数路径就有用武之地。例如,在无权迷宫中找到合法移动次数最少的路线、确定两个账号之间最少需要经过多少条关系链接,以及判断能否在给定的转换次数内到达某个状态。在形式验证中,对有限状态模型执行 BFS,可以生成到达错误状态所需转换次数最少的反例。这种轨迹最短,指的是转换次数最少,而不一定是实际执行时间最短,也不一定是向人解释时篇幅最短。

BFS 也可作为更复杂图算法中的子程序。Edmonds–Karp 最大流算法使用 BFS,在残量网络中选择边数最少的增广路径,其最坏情况下的运行时间为 O(∣V∣∣E∣2)O(|V||E|^2)。Hopcroft–Karp 二分图匹配算法先通过一个 BFS 阶段建立与最短增广路径相对应的分层结构,再通过搜索找出一组符合要求的此类路径。对于具有 nn 个顶点和 mm 条边的二分图,该算法的标准时间复杂度界为 O(mn)O(m\sqrt{n})。

有些应用看起来类似于 BFS,却并不完全符合其模型。网络爬虫可以根据网页与初始页面之间的超链接距离来确定抓取优先级,但由于网络延迟、针对不同主机的调度以及持续变化的内容,简单的先进先出抓取方式未必能与教科书中对固定图的遍历相一致。同样,实际的路由系统通常优化的是带权的管理指标或性能指标,而不仅仅是最小跳数。

并行遍历与大规模实现

BFS 的分层结构天然适合并行计算。层同步实现并不让各个工作线程操作同一个顺序队列,而是维护当前前沿 FkF_k。工作线程并发处理其中的顶点,发现此前未访问过的邻接顶点,并构建下一层前沿 Fk+1F_{k+1}。相邻两层之间通过同步步骤分隔,因此即使同一层内的处理顺序不可预测,算法仍能保证最短路径的含义不变。

并行处理同一层时,正确性方面的主要问题是重复发现。两个工作线程可能同时遇到同一个尚未发现的顶点。原子的测试并置位或比较并交换操作,可以确保只有一个工作线程成功认领该顶点,并将其加入下一层前沿。来自同一层的所有竞争性发现都对应相同的距离,因此,要保证距离正确,通常不必确定唯一的前驱;但要构建有效的父节点树,唯一前驱就很有用。具体由哪个前驱胜出,可能因运行而异。

图的结构对性能有很大影响。如果每个工作线程都以完整顶点为单位分配任务,一个拥有数百万个邻接顶点的顶点就可能造成严重的负载不均衡。将邻接表的不同区段分配给不同工作线程可以缓解这一问题,但会增加调度开销。稀疏、不规则的访问也会限制 CPU 缓存的局部性,使内存带宽和访问延迟成为主要影响因素。在图形处理器上,数千个线程可以并发检查边,但顶点度数的差异,以及发现顶点时的操作争用,会增加高效执行的难度。

方向优化 BFS 改变了生成某一层的方式。在通常的自顶向下方式中,算法沿当前前沿顶点的出边进行探索。而在自底向上的步骤中,算法扫描尚未发现的顶点,检查当前前沿中是否存在符合条件的前驱。一旦找到这样的前驱,就可以停止对该顶点的扫描。对于有向图,这一操作需要能够访问入边邻接信息。当一个较大的前沿很可能触及许多剩余顶点时,在这两种模式之间切换可以大幅减少需要检查的边数。不过,这种做法并非对所有图或每一层都有利。

在分布式计算中,顶点和边被划分到不同机器上。发现归远程机器所有的邻接顶点时需要通信,而将消息成批发送可以减少开销。BFS 的每一层都可能既需要交换数据,又需要在全局范围内判定本层是否完成。跨分区边较多的图会产生大量网络流量;而层数多、每层顶点数少的图,即使每层真正要做的工作相对较少,也可能反复承担同步开销。

2010 年推出的 Graph500 基准测试,推动 BFS 成为数据密集型高性能计算中的一项重要工作负载。其测量重点是图遍历吞吐量,而非浮点运算能力。因此,大规模 BFS 展现了一个更普遍的体系结构问题:即便算法具有简单的线性工作量界限,如果其主要操作涉及不规则的数据移动、通信与协调,仍然可能难以加速。

历史发展与实现实践

BFS 源于早期对系统化搜索和最短路径的研究。爱德华·F. 摩尔在 1959 年的论文《穿越迷宫的最短路径》中,描述了一种通过逐层扩展来寻找迷宫路径的方法。C. Y. 李在 1961 年的论文《路径连接算法及其应用》中,提出了用于连接问题的波传播布线方法。李氏算法后来尤其常用于网格布线:从源点开始,标号逐层向外扩散,直到到达目标点,再沿标号递减的方向回溯。

这些方法在实际应用场景中明确体现了按距离分层的原则。网格为此提供了直观的图景:波先到达所有只需移动一步的位置,再到达所有需要移动两步的位置,依此类推。只要用邻接表或后继状态生成过程来替代几何上的相邻关系,同样的原则就能推广到任意图。此后,BFS 成为图算法、人工智能搜索和算法教学中的标准方法。

可靠的 BFS 实现与仅在形式上类似 BFS 的代码,在若干实现细节上有所区别。队列必须支持高效地从队首移除元素。反复删除连续数组的第一个元素,可能导致其余元素不断移位,使原本为线性时间的遍历仅在队列管理上就产生平方级的工作量。环形缓冲区、合适的双端队列,或使用单调递增队首索引的数组,都能避免这一问题。当每个顶点最多入队一次时,容量为 ∣V∣|V| 的数组就足以用作队列。

对于隐式图,如何判定已访问状态是否相同也同样重要。描述同一谜题配置的两条记录,即使由不同的动作序列生成,也必须判定为同一个状态。反过来,如果两个状态所包含的信息会影响后续动作是否合法,就不能将它们合并。例如,当后续移动取决于已经收集了哪些钥匙时,仅用位置不足以描述状态;状态还必须包含钥匙集合。如果通过哈希来实现相等性判定,就必须用适当的相等性检查来处理哈希冲突,而不能自动把发生冲突的记录视为同一状态。

要保证结果可复现,还需要作出额外规定。BFS 算出的距离与邻居的排列顺序无关,但遍历顺序和父节点的选择通常会受其影响。对邻接表排序或规定稳定的处理顺序,可以使串行执行的结果可复现,但会增加预处理成本。如果要求每次执行都生成完全相同的父节点树,并行实现可能需要明确规定如何打破平局。没有这一要求时,前一距离层中任何符合条件的父节点都可以采用。

BFS 的结果也可以直接进行一致性检查。源点的距离必须为零;每个可达的非源点顶点都必须有一个通过边与之相连的父节点,并满足 d[v]=d[parent[v]]+1d[v]=d[parent[v]]+1。从可达顶点出发的每条出边,都必须指向一个可达顶点,并满足 d[v]≤d[u]+1d[v]\leq d[u]+1。父节点路径证明了所记录的路径长度确实可以达到,而边上的不等式则排除了更短路径的可能性。这些性质使我们无需再执行一次遍历来复现相同的队列顺序或父节点选择,就能验证结果。