默登公司光导纤维网络的最小生成树问题

默登（Modern）公司的管理层决定铺设最先进的光导纤维网络，以便在它的主要中心之间提供高速通信（数据、声音和图像）。图6-30中的节点显示了该公司主要中心（包括该公司的总部、巨型计算机、研究区、生产和配送中心）的分布图。虚线是铺设纤维光缆可能的位置（其他的两个中心之间也可能铺设光缆，但由于不经济已经排除在外了），每条虚线旁边的数字表示如果选择在这个位置铺设光缆需要花费的成本（单位：百万美元）。

图6-30

图6-30 显示了默登公司主要中心（节点）、纤维光缆（虚线）的可能布局和这些光缆的成本（单位：百万美元）。为了充分利用光纤技术在中心之间高速通信的优势，不需要在每两个中心之间都用一条光缆把它们直接连接起来，而那些需要光缆直接连接的中心有一系列的光缆连接它们。现在的问题就是要确定需要铺设哪些光缆使得提供给每个中心之间的高速通信的总成本最低。实际上，这就是一个最小支撑树问题。

在所有的备选边（图中的虚线）里，因为在节点C 和节点D 之间的边以及节点E 和节点F 之间的边的成本是最低的（成本为1），所以第一步，我们需要选择其中的一条备选边为插入到网络中的第一条边。让我们选择节点C 和节点D 之间的边（另外一条会在后面被选中），如图6-31 所示。

图6-31

其次，由一条边连接起来的两个节点是节点C 和D，所以需要比较在这两个节点中任一个节点与还没有与边连接的节点间备选边的成本。这些备选边及其成本为：

由于在这些边中成本最低的是节点C 和节点B 之间的边，其成本为2，所以选择它作为插入网络的下一条边，如图6-32 所示。

图6-32

现在，节点B，C 和D中的每一个都和一条边相连（或者是节点C 和两条边相连），所以，在下一次选节点时需要比较这些节点与其他节点间的备选边的成本：

在这些备选边中成本最低的是节点B 和节点A 之间的边，所以，它成为下一条插入到网络中的边，如图6-33 所示。

图6-33(www.xing528.com)

因为现在节点B，C 和D 都有边与其相接，所以接下来比较这些节点和那些还没有边连接的节点之间的备选边的成本（实际上，所有这些备选边都不会涉及节点A，这是因为没有一条连在A 点的边可以连接到那些没有连在边上的节点）：

成本最低的备选边是节点C 和节点F 之间的边，所以将其添加到网络中，如图6-34 所示。

图6-34

现在除了节点E 和节点G 外，所有节点都和边连接上了。因此，下一步唯一需要考虑的备选边是节点E 或节点G 与其他节点之间的边。

到目前为止，成本最低的备选边是节点F 和节点E 之间的边，所以将其添加到网络中（记得这条备选边与第一步中被选择插入到网络中的初始边成本相同），如图6-35 所示。

图6-35

现在，由于节点G 是唯一没有边连接的节点，所以接下来唯一要考虑的是这个节点和其他节点之间的备选边。

本例成本较低的备选边是节点E 和节点G 之间的边，所以我们将其添加到网络中，如图6-36 所示。

图6-36

现在每一个节点都和边接上了，算法结束，这就是我们的最优解。所有插入到网络中构成最小支撑树的边的总成本为2+2+1+3+1+5=14（1400 万美元）。所有剩下的备选边（虚线）被抛弃了，因此已经插入到网络中的边为每两个节点之间提供了一条路。