通信网络架设中最小生成树问题的一种新算法

邓超等

摘 要：本文在Prim算法的基础上，结合最优二叉树的思想，提出了一种新的计算方法，将最小生成树的生成过程划分为几个连通子图的最小生成树生成过程，从而显著的提高算法效率。

关键词：网络；最小生成树；算法

1 基本思想

传统的Prim算法是一种基于边的算法，从连通网络G=（V，E）的某一顶点出发，选择与它关联的具有最小权值的边（u0，v），将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边（u，v），把它的顶点加入到集合U中，如此下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止，这时就可构造一棵最小生成树。

在实际编程过程中，如果边的数量较多，则该算法可能在寻找权值最小的边（u，v）时花费较多时间。若借鉴最优二叉树的思想，将一个大图划分为几个连通子图，则能显著的提高算法的效率。

最优二叉树的思想是在n个结点中，每次找出权值最小的两个结点，合并成一个新的父结点，其权值为这两个结点的权值之和，并删除原来的两个子结点；然后继续在这n-1个结点中找出权值最小的两个结点，合并生成一个新的父结点，并删除这两个最小的结点。直到最后剩下唯一的结点就是最优树的根结点。

基于这种想法，本文提出一种新的最小生成树算法：其算法描述为：

⑴对于连通网络G=（V，E），从图中vi出发，寻找与vi相连，权值最小的边（vi，vk），k>i，对于第一步，我们取i=1。

⑵vi、vk、边（vi，vk）构成一连通子图，记为 ，将s=（vi，vk）加入到最小生成树的集合S中。

⑶在原图中，把 看成一个结点，代替vk的位置。则图中其余结点到 的距离为 。

⑷依次对v2、v3、……、vn-1进行上述操作，最后得到的 为包含所有结点的集合， 即所求的最小生成树。

注：在循环进行该算法时，必然会碰到一个连通子图与一个顶点或另一个连通子图进行合并操作的情况，因为在合并操作中有可能会混乱权值与其相对位置所对应的起始点信息，因此，我们设定在连通网络G=（V，E）所对应的对称矩阵中，每一个元素为包含了起始点、权值两部分信息的一个对象，为方便表示，仍然只显示权值信息。在具体操作时， 为一对象赋值操作，同时对起始点、权值数据进行操作。

采用该算法，向集合U增加第i个结点时，在最坏的情况下（网络为全连通网络）只需要比较与当前结点相连的n-i条边即可。总共比较（n-2）*（n-1）/2次，相当于n-1条边的排序操作复杂度。而传统Prim算法增加第一个结点时，在最坏情况下需要对n*（n-1/2）条边进行权值排序操作。后续增加结点到集合U中时，仍然每次都需要遍历所有的边。因此，本文提出的算法在边密集的情况下能够显著提高运算效率。

2 实例分析

假设在七个城市架设通信网络系统，任意两个城市之间都可直接架设通信网络，最终目标是以最小总费用在七个城市架设通信网络系统。表1为通过各城市之间架设通信线路的工程经费。

因为任意两个城市之间都可直接架设通信网络，并且网络连接无方向性，所以七城市之间的连接图如图所示可以认为是一个无向连通赋权图G（V，E，W），其中，V表示顶点集，E表示边集， W表示比较因子的集合。这样间题就转化为一个图论问题，可以把影响问题的两个元素看作一个因素，即把比较因子wi作为路径长度ei的权值因子，问题进而转化为一个在无向连通赋权图 G（中求解一棵最小代价生成树的问题。

图1网络表示五个城市以及五个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋予边的权值表示相应的架设费用。具体的以R1～R5代表五个城市， R1～R5（各城市）之间以边相连，每条边代表五个城市间可能设置的通信线路，赋予边的权值表示相应的架设费用。

对于该问题，我们从R1出发：

⑴寻找出与R1相连的最短边e1，4=1，

⑵将R1、R4融合为一连通子图R4'，通过公式：

计算出R4'与剩下各点的距离，并将e1，4加入到最小生成树 S中：

⑶将R4'代替原R4，则权值矩阵变为：

现权值矩阵中，

原网络图变为：

重复上述步骤，对R2找出后续最小权值边为e2，3=1，将R2，R3合并为一连通子图R3'，代替原有的R3，同时将e2，3加入到最小生成树S中。

连通矩阵为：

原网络图变为：

对R3'，找出后续最小权值边为e3，4=3，将R3'，R4'合并为连通子图R4''，同时，将（R3'，R4'）=（R3，R4）加入到最小生成树 中。

因 ，均有 ，故在这一步没有改写权值矩阵。连通矩阵不变，原网络图变为：

对R4''，找出后续最小权值边为e4，5=1，将R4''，R5合并为连通子图R5'，同时，将（R4''，R5）=（R1，R5）加入到最小生成树S中。因R5已是最后一个结点，运算结束，得到最小生成树：

即：

3 结论

通过上述计算过程，我们可以发现，改进后的算法，将原先的复杂度较大的排序计算分割为 个小规模的排序计算，在计算网点多，连接关系复杂的网络时，能够显著提高运行效率。

[参考文献]

[1]杨成慧，殷红，孟建军，姜虎强.基于Prim算法的通信网络架设仿真研究与应用[J].计算机仿真.2007年10月.

[2]谢力军，李晓梅，何佳，杨军.基于模糊最小生成树的通信网络架设模型[J].吉首大学学报（自然科学版）.2010年04期.