Question

7.22.Prim生成树算法

对于我们最后的图算法，让我们考虑一个在线游戏设计师和网络收音机提供商面临的问题。 问题是他们想有效地将一条信息传递给任何人和每个可能在听的人。 这在游戏中是重要的，使得所有玩家知道每个其他玩家的最新位置。 对于网络收音机是重要的，以便所有该调频的收听者获得他们需要的所有数据来刷新他们正在收听的歌曲。 Figure 9 说明了广播问题。

Figure 9

这个问题有一些强力的解决方案，所以先看看他们如何更好地理解广播问题。这也将帮助你理解我们最后提出的解决方案。首先，广播主机有一些收听者都需要接收的信息。最简单的解决方案是广播主机保存所有收听者的列表并向每个收听者发送单独的消息。在 Figure 9中，我们展示了有广播公司和一些收听者的小型网络。使用第一种方法，将发送每个消息的四个副本。假设使用最小成本路径，让我们看看每个路由器处理同一消息的次数。

来自广播公司的所有消息都通过路由器 A ，所以 A 看到每个消息的所有四个副本。路由器 C 只接收到其收听者每个消息的一个副本。然而，路由器 B 和 D 将收到每个消息的三个副本，因为路由器 B 和 D 在收听者 1,2和3 的最短路径上。当广播主机必须每秒发送数百条消息用于无线电广播，这是很多额外的流量。

暴力解决方案是广播主机发送广播消息的单个副本，并让路由器整理出来。在这种情况下，最简单的解决方案是称为 不受控泛洪 的策略。洪水策略工作如下。每个消息开始于将存活时间（ttl）值设置为大于或等于广播主机与其最远听者之间的边数量的某个数。每个路由器获得消息的副本，并将消息传递到其所有相邻路由器。当消息传递到 ttl 减少。每个路由器继续向其所有邻居发送消息的副本，直到 ttl 值达到 0。不受控制的洪泛比我们的第一个策略产生更多的不必要的消息。

这个问题的解决方案在于建立最小权重 生成树。正式地，我们为图 $G=(V,E)$G=(V,E)定义最小生成树 T 如下。 T 是连接 V 中所有顶点的 E 的非循环子集。 T中的边的权重的和被最小化。

Figure 10 展示了广播图的简化版本并突出了生成图的最小生成树的边。现在为了解决我们的广播问题，广播主机简单地将广播消息的单个副本发送到网络中。每个路由器将消息转发到作为生成树的一部分邻居，排除刚刚向其发送消息的邻居。在这个例子中 A 将消息转发到 B，B 将消息转发到 D 和 C。D 将消息转发到 E，E将它转发到 F，F 转发到 G。没有路由器看到任何消息的多个副本，所有感兴趣的收听者都会看到消息的副本。

Figure 10

我们将用来解决这个问题的算法称为 Prim 算法。 Prim 算法属于称为 “贪婪算法” 一系列算法，，因为在每个步骤，我们将选择最小权重的下一步。 在这种情况下，最小权重的下一步是以最小的权重跟随边。 我们的最后一步是开发 Prim 算法。

构建生成树的基本思想如下：

While T is not yet a spanning tree
   Find an edge that is safe to add to the tree
   Add the new edge to T

诀窍是指导我们 “找到一个安全的边”。我们定义一个安全边作为将生成树中的顶点连接到不在生成树中的顶点的任何边。这确保树将始终保持为树并且没有循环。

用于实现 Prim 算法的 Python 代码如 Listing2 所示。Prim 算法类似于Dijkstra 算法，它们都使用优先级队列来选择要添加到图中的下一个顶点。

from pythonds.graphs import PriorityQueue, Graph, Vertex

def prim(G,start):
    pq = PriorityQueue()
    for v in G:
        v.setDistance(sys.maxsize)
        v.setPred(None)
    start.setDistance(0)
    pq.buildHeap([(v.getDistance(),v) for v in G])
    while not pq.isEmpty():
        currentVert = pq.delMin()
        for nextVert in currentVert.getConnections():
          newCost = currentVert.getWeight(nextVert)
          if nextVert in pq and newCost<nextVert.getDistance():
              nextVert.setPred(currentVert)
              nextVert.setDistance(newCost)
              pq.decreaseKey(nextVert,newCost)

Listing 2

下面的图（Figure 11 到 Figure 17）展示了在我们的样本树上运行的算法。我们从起始顶点开始。到所有其他顶点的距离被初始化为无穷大。看看 A 的邻居，我们可以更新另外两个顶点 B 和 C 的距离，因为通过 A 到 B 和 C 的距离小于无限。这将 B 和 C 移动到优先级队列的前面。通过将 B 和 C 的前导链接设置为指向 A 来更新前导链接。重要的是要注意，我们还没有正式向生成树添加 B 或 C。在将节点从优先级队列中删除之前，不会将其视为生成树的一部分。

因为 B 有最小的距离，我们看看 B。检查 B 的邻居，我们看到 D 和 E 可以更新。D 和 E 都获得新的距离值，并更新它们的前导链接。移动到优先级队列中的下一个节点，我们找到 C。只有仍在优先级队列中的节点是 F，因此我们可以更新到 F 的距离，并调整优先级队列中的 F 的位置。

现在我们检查与节点 D 相邻的顶点。我们发现可以更新 E 并​​且将从距离 6 减小到 4。当我们这样做时，我们将 E 上的前趋链接改变为指向 D，从而准备移植到生成树中不同的位置。算法的其余部分按照预期进行，将每个新节点添加到树中。