最小生成树的算法――减枝算法

摘要：最小生成树是数据结构中图的一种重要应用，对于具有n个顶点的带权连通图可以建立许多不同的生成树。Kruskal算法和Prim算法是求最小生成树的常用算法。本文讨论了一种新的算法。

关键词：最小生成树；pirm算法；kruskal算法

中图分类号：TP311.12 文献标识码：A文章编号：1007-9599 (2011) 09-0000-01

Minimum Spanning Tree Algorithm- Branch Cut Algorithm

Liu Xin

(School of Information Resource Management,Renmin University of China,Beijing100872,China)

Abstract:Minimum spanning tree data structure is an important application in,for nvertices with weighted connected graph spanning tree can create many different.This article discusses a new algorithm.

Keywords:Minimum spanning tree;Pirm algorithmKruskal algorithm;

一、引言

在现实社会中，常常会遇到有关于n个城市之间建立通信联络网，不同城市间建立的代价各不相同。N个小区需要铺设管道，不同小区之间的代价也不同。这样，我们自然会考虑这样一个问题，怎么样在最节省的情况下（代价最小）建立一个是所有不同点都联通的网络。实践中应用于线路、管道辅设、运输问题设备更新决策等。现在，我们考虑的就是怎么样找到一颗生成树，使得总的耗费最少。

最小生成树的构造准则：

1.必须只使用该网络中的边来构造最小生成树；2.必须使用且仅使用n-1条边来连接网络中的n个顶点；3.不能使用产生回路的边。

最小生成树问题的解法主要有三种：Prim算法，Kruskal算法和“破圈”算法。

Prim和kruskal这两种算法是按权值递增的顺序构造连通网的最小生成树.

二、算法实现的思路

现在最常使用的prim算法和kruskal算法的基本思路均为避圈法，均为一种贪心算法。

Prim算法是利用MST性质找到最初的连通图，并一步步找到使不在连通图中的点与连通图连接而代价最小的边，因对于每一个点来说，只会将它与连通图连接一次，所以prim算法会保证生成树不会成环。

Kruskal算法则是直接利用了避圈的思路，每一次找到不使图构成环的代价最小的边，根据MST性质我们易知找到的第一条边就是图中代价最小的边。之后每次找到代价最小而不会构成环的边，在将所有点连通时停止，即得到最小生成树

本文主要论述的是在考虑图中所有点和所有有权的边时，尽量“贪心”的删除权较大的边，并保证图是联通的。一直剪至n-1条边时，不能继续剪枝。

三、算法过程

（一）算法中用到的变量。1.二维数组a[n][n]为带权无向图的邻接矩阵，其中若Vi与Vj之间有边且权为w，则a[i][j]=w，否则a[i][j]=0。2.二维数组b[n][4]是所有边按照权值由大到小排序的数组，其中包括边的权值，边的位置p，q，变量p，若找到的要删去的边是Vi与Vj之间的边，则将a[i][j]和a[j][i]置为0，表示这两点之间的边已删去；临时变量am来标记找到的最大元素（am是为了保护权值大但不能删的边），如果找到的元素a[i][j]不能删去，则可以让a[p][q]=am，a[q][p]=am来还原刚才删去的边，变量i，j为二维数组的行标和列标，变量sm为计算器，用来存储图的边数，邻接矩阵A的上三角矩阵中非零元的个数就是sm的值，每删去一边，sm就减去1，当sm=n－1（因为树的边数等于结点数减1）时，结束。

（二）算法中要用到的子程序。1.子程序Wshall（）的功能是通过图的邻接矩阵求出可达矩阵，通过可达矩阵来判断一个图是否连通，该子程序用来检测删去边后得到的图是不是还连通，如不连通，则将删去的边恢复后再找另外的符合条件的边删去，再进行检测。2.子程序Input（）用来输入邻接矩阵。同时构建一个b[n][4]的数组：分别为：权值，行值，列值，next。并根据输入的数据从大到小排序。3.子程序Output（）用来输出邻接矩阵。

（三）主程序main（）的基本流程

第一步：调用子程序Input（）输入带权邻接矩阵A

第二步：统计出带权图的边数sm，此时用一个while循环来进行下一步，其循环条件是：sm！=n-1，如果smn-1，则继续下一步。Sm=n-1而且图又连通的话，该图就是一棵生成树。

第三步：调用子程序Max（）查找要删去的边。

第四步：调用子程序Wshall（）判断删去边后的图是否还连通。如果连通则继续找下一边，如果不连通则将删去的边还原后再找其他的符合条件的边。直到循环结束。

第五步：输出最后求出的最小生成树的带权邻接矩阵，并统计出该最小生成树的权值。

四、算法正确性论证

（一）用n-1条边连接n个点。首先证明n个点需要大于等于n-1条边才能联通（易证），再证明大于n-1条边时肯定能删除边且不影响所有点的连通性。当有n个点和n条边的图是全连通的时候，在每两个点之间只能有一条边的条件下，可以证明图中肯定有环，所以能够在环中找出权最大的一条边并删掉这条边，而不会影响连通性。

（二）MST性质。反证法：假设代价最小的边e1不在最小连通图中。根据算法可知，e1是最后被删掉的，而e1可以被删掉，则有另外一条边或者几条边可以使两个边连通，又因为所有的边都比e1的代价大，所以在判断另一条边的时候就应该删掉，而如果最后删掉e1这条边必定会使某个点不连通，则构成的不是最小生成树。反证得e1边一定在最小生成树种，符合MST性质。

（三）N-1条边的集合是全体边集合的子集。最小生成树的构成是从完全图开始删除一些边，最后没有删除的边的集合构成最小生成树，所以最小生成树一定是全体边集合的子集。

参考文献：

[1]徐磊,章兢.广义最小生成树的遗传算法求解及应用[J].系统工程与电子技术,2004,26(3):3

[2]陈国龙,郭文忠,涂雪珠等.求解多目标最小生成树问题的改进算法[J].软件学报,2006,17(3):7

[3]王涛,李伟生.低代价最短路径树的快速算法[J].软件学报,2004,15(5):6