2.3　广度优先搜索树的构建

在同步系统中，洪泛算法是构建广度优先搜索（BFS）生成树的一种简单而有效的方法。然而，在异步系统中，由洪泛算法构建的生成树可能远离BFS。在本节中，我们将两个经典的BFS构造——Dijkstra和Bellman-Ford——作为异步算法来实现。

我们从Dijkstra算法开始。其基本思想是始终将最近的节点添加到BFS树的现有部分。我们需要通过逐层开发BFS树来并行化这个想法。该算法分阶段进行。在第p阶段，检测与根（第p层）有距离p的节点。

算法2.11　Dijkstra BFS

1.我们从阶段p=1开始，有一棵树T，其为根加上根的所有近邻

2.repeat

3.　根通过在T内广播“start p”来启动阶段p

4.　当接收到“start p”，T的叶节点u（即p级节点）向所有安静的邻节点发送“join p+1”消息（如果u还没有和v交流，那么邻居v为安静的。）

5.　如果尚未在T中的节点v接收到一个“join p+1”消息，则节点v以“ACK”回应，并成为树T的p+1层新的叶子

6.　如果节点v已经在T中，则节点v将以“NACK”回应所有“join”消息

7.　T的叶节点在p层收集所有邻节点的应答；然后叶子开始一个回传给根的回传算法

8.　当回传过程在根节点结束时，根节点增加相位

9.until没有新的节点被检测出来

定理2.12　算法2.11的时间复杂度为O（D2），消息复杂度为O（m+nD），其中D是图的直径，n是节点数，m是边的数量。

证明：BFS树中的广播/回传算法最多需要2D时间。在叶子上寻找新邻居需要2个时间单位。由于BFS树的高度受直径的限制，我们有D个阶段，总的时间复杂度为O（D2）。每个参与广播/回传的节点在广播时最多只接收1个消息，在回传时最多只发送1个消息。由于有D个阶段，所以成本以O（nD）为界。在每条边上最多有2个“join”消息。对“join”请求的答复是1个“ACK”或“NACK”，这意味着我们在每条边上最多有4个额外的消息。因此，消息的复杂度是O（m+nD）。

备注：

●时间复杂度并没有让人非常兴奋，让我们试试Bellman-Ford的方法吧！

Bellman-Ford的基本思想更简单，而且在互联网中大量使用，因为它是无处不在的边界网关协议（BGP）的一个基本版本。其想法是简单地保持到根的距离的准确性。如果邻居找到了通往根的更好的路线，节点可能也需要更新其距离。

算法2.13　Bellman-Ford BFS

1.每一个节点u存储着一个整数du，其与u到根之间的距离相关。初始，对于其他每个节点u（droot且du=∞）

2.根通过将“1”发送给所有的邻节点开始算法

3.if一个节点u从邻节点v接收到一个消息“y”且y＜du then

4.　节点u设置du:=y

5.　节点u发送“y+1”给所有的邻节点（除了v）

6.end if

定理2.14　算法2.13的时间复杂度为O（D），消息复杂度为O（nm），其中D，n，m的定义与定理2.12相同。

证明：我们可以通过归纳法证明时间复杂度。我们声称离根节点的距离为d的节点在时间d之前已经收到了一个消息“d”。根在时间0时就知道自己是根。一个距离为d的节点v有一个距离为d-1的邻居u。节点u通过归纳法在时间d-1或之前向v发送一个消息“d”，然后v在时间d或之前收到这个消息。消息的复杂度比较容易：一个节点可以减少其距离最多n-1次；每一次它都向所有的邻居发送一个消息。如果所有节点都这样做，那么我们就有O（nm）条消息。

备注：

●算法2.11具有更好的消息复杂度，算法2.13具有更好的时间复杂度。目前最好的算法（优化两者）需要O（m+n log3 n）消息和O（D log3 n）时间。这种权衡算法超出了本章的范围，但我们以后将学习一般的技术。