边权相同的最小生成树改进算法

2015-08-09刘宏兵司倩楠

信阳师范学院学报（自然科学版） 2015年4期

薛瑞,刘宏兵，司倩楠

(信阳师范学院计算机与信息技术学院, 河南信阳 464000)

0 引言

最小生成树(Minimum Spanning Tree，MST)是图论研究中一个经典的问题，许多网络优化和运筹学问题都可以利用最小生成树来解决.最小生成树旨在赋权连通图中寻找一些能到达各点而且边权总和最小的优化模型.近年来，国内外对最小生成树的研究非常活跃，这些研究主要集中在最小生成树算法的改进及最小生成树的应用两方面.例如，文献[1]提出了最小生成树的DNA算法，文献[2-4]分别提出了最小生成树在聚类算法中的应用，文献[5]提出了最小生成树在图像分割中的应用，文献[6]提出了最小生成树在图像融合算法中的应用.Tewarie等[7]研究了最小生成树在脑网络分析中的应用，Ruiz等[8]研究了最小生成树在密码学中的应用，Ahmadi等[9]研究了如何应用最小生成树使得网络再配置中损失达到最小.

到目前为止，求解最小生成树常用的算法有Kruskal算法[10]、Prim[11]算法和避圈法[12]等.当一个赋权的连通图中多条边的权值相同时,最小生成树的形式可能不唯一.权值相同的最小生成树涉及通信、网络布线、道路交通等很多领域，然而在国内外众多的研究成果中，这方面的研究几乎没有.本文基于Kruskal算法，针对权值相同的边，提出了改进的最小生成树算法.

1 最小生成树的Kruskal算法

Kruskal算法是寻找最小生成树的一种贪心算法，在算法的每一步，都从剩下的可用数据中做出一个最优选择，而且如果局部最优(比如对于顶点a和与a邻近的点)可以导致整体最优.

1.1 算法概述

给定连通带权图G，设G有n个点，m条边.边集E={e1，e2，…，em}.

Step1 选取最小权边e1，置边数i←1.

Step2i=n-1结束，否则转Step3.

Step3 设已选择边为e1，e2，…，ei，在G中选取不同于e1，e2，…，ei的边ei+1，使得{e1，e2，…，ei，ei+1}无回路且ei+1是满足条件的最小边.

Step4i←i+1，转Step2.

1.2 算法分析

Kruskal算法常被用于求解边稀疏的网络最小生成树问题，假设一个图有n个点，该算法每次选择n-1条边，所使用的贪婪准则是从剩下的边中选择一条不会产生回路的权值最小的边加入已选择的边的集合中，其时间复杂度为O(elog2e).当图中存在两条权值相同的边时，利用Kruskal算法，如果保留其中的一条边不会产生回路，但同时保留两条会有回路时，算法会自动将第二条边删除，继续在剩余的边中寻找权值最小的边.然而实际上，如果用删除掉的那条边代替保留生成树中的那一条，有可能会得到另一棵生成树.

因此，当图中存在权值相同的边时，利用Kruskal不能保证可以找到所有的最小生成树.如图1中赋权连通图G1，利用Kruskal算法在Matlab中进行求解，结果只能得到一颗最小生成树(v1,v3)，(v1,v4)，(v5,v6)，(v4,v6)，(v1,v7).

图1 赋权连通图G1Fig. 1 Weighted connected graph G1

而实际上相同权和的最小生成树还有(v1,v3)，(v1,v4)，(v5,v6)，(v3,v5)，(v1,v7)与(v1,v3)，(v1,v4)，(v5,v6)，(v4,v6)，(v2,v4)及(v1,v3)，(v1,v4)，(v5,v6)，(v3,v5)，(v2,v4)等最小生成树.

2 边权相同的最小生成树改进算法

针对图中存在权值相同的边时，Kruskal算法不能找到所有的最小生成树，从而造成决策方案丢失的情况，提出改进的最小生成树算法.

2.1 边权相同的两条边

边权相同的两条边在构造最小生成树时共有以下4种分布情况:

①两条边均可保留，如图G2中的边(v1,v2)与边(v2,v3).

②两条边只有1条可以保留，如图G2中的边(v3,v5)与边(v3,v6)，根据Kruskal算法，在遍历流程中保留边(v3,v5)不会产生回路，但保留边(v3,v6)会产生回路.

③两条边均不可保留，如图G2中的边(v1,v3)与边(v1,v4)；在遍历过程中，无论保留哪一条都会产生回路；

④两条边可任意保留一条，但不可同时保留，如图G1中的边(v4,v6)与边(v3,v5),在遍历过程中，无论保留哪一条都不会产生回路，但同时保留两条边会产生回路.

图2 赋权连通图G2Fig. 2 Weighted connected graph G2

利用Kruskal算法之所以不能找到所有权值最小的生成树，是因为该算法中忽略了上述中的第④种情况中权值相同的边对最小生成树结果的影响.针对第④种状况，以下定理成立.

定理1 赋权连通图G的任意两条权相同的两条边ei和ej，若ei与G中任意边e构成回路，则ej也和e构成回路.

证明如图3，根据Kruskal算法，首先将权为1，2，3的边置于生成树中，在剩下的边中存在两条权最小的边(v3,v4)，(v5,v6).两条边任取一条置于树中都不会产生回路，但若两条边都保留，则会产生回路.

在图G中任取一条与(v3,v4)产生回路的边，取法有两种.

①在边(v3,v4)，(v5,v6)围成的回路内任取一条边.如图3，连接边(v1,v5)，则该边把由边(v3,v4)，(v5,v6)围成的回路v1→v3→v4→v5→v6→v1分成了两个子回路v1→v5→v6→v1与v1→v3→v4→v5→v1.

图3 赋权连通图GFig. 3 Weighted connected graph G

②在边(v3,v4)，(v5,v6)围成的回路外任取一条边.如图3，连接边(v2，v4)，则边(v2，v4)与边(v2，v3)、(v3，v4)围成一个回路v2→v4→v3→v2，去除边(v3，v4)，边(v2，v4)仍然可以和边(v5，v6)围成回路v1→v6→v5→v4→v2→v3→v1.证毕.

由定理1，可得定理2成立.

定理2 赋权连通图G的任意两条权相同的两条边ei和ej，若ei与G中任意边e不构成回路，则ej也与e不构成回路.

设T0是已求得的一棵最小生成树，在最小生成树不唯一的情况下，存在其他的生成树T，称T-T0得到的边集长度为距离[6](这里的长度是指集合中元素的个数).结合定理1与定理2得出以下结论成立.

定理3 赋权连通图G有且只有两条权相同的两条边ei和ej，其中ei,ej的分布如上所述的第④种状况，设T1是包含边ei的最小生成树，T2是包含边ej的最小生成树，则T1-T2=T2-T1.

一般情况下，若赋权连通图G中权值为w1的边有n1条，权值为w2的边有n2条,…,wt的边有nt条,且权值相同得边均如上述的第④种分布状况，则图G的最小生成树共有n1×n2×…×nt条.

2.2 改进算法的步骤

设G=〈V,E〉是一个简单的赋权连通图，其中|V|=n并且每条边都赋值为一个正实数w(e).

Step0 令i=1,j=0,T=φ.把G的边按照权由小到大排列，即w(e1)≤w(e2)≤…≤w(em).

Step1 判断T∪{ei}是否含圈.若不含圈,转Step3.若含圈，验证ei=ei-1是否成立，若ei≠ei-1，转Step2;若ei=ei-1,验证T-{ei-1}∪{ei}是否含圈.若含圈，转Step2;若不含圈，则T=T或T=T-{ei-1}∪{ei}.

Step2 令i=i+1.若i≤m,转Step1;否则结束,此时G不连通,所以没有最小树.

Step3 令T=T∪{ei},j=j+1.若j=n-1,则结束，T是最小树;否则，转Step1.

3 应用实例

以信阳师范学院交通路线图作为网络拓扑图.随着校园规模的不断扩大，现要对校园的通讯光缆进行重新改造.为了施工的便利，光缆线通常是沿着道路两端铺设的.把信阳师范学院每个道路交叉口当成一个结点，各点之间的连线表示两交叉口之间的距离(单位：m).如图4所示.

根据改进的最小生成树算法原理，最优的施工方案有：

T1:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v1,v4)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v19,v21),(v7,v10)，(v2,v3).

T2:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v1,v4)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v18,v21),(v7,v10)，(v2,v3).

T3:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v2,v5)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v19,v21),(v7,v10)，(v2,v3).

T4:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v2,v5)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v18,v21),(v7,v10)，(v2,v3).

T5:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v1,v4)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v19,v21),(v8,v9)，(v2,v3).

T6:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v1,v4)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v18,v21),(v8,v9)，(v2,v3).

T7:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v2,v5)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v19,v21),(v8,v9)，(v2,v3).

T8:(v6,v7)，(v17,v20)，(v11,v13)，(v18,v20)，(v4,v8),(v5,v7)，(v1,v2)，(v4,v5)，(v9,v10)，(v18,v19),(v2,v5)，(v15,v17)，(v16,v17)，(v10,v11)，(v19,v22)，(v14,v17)，(v10,v18)，(v11,v12)，(v18,v21),(v8,v9)，(v2,v3).