利用找环去边法求最小生成树的算法探析.docx

2002年9，丁襄樊学院学报 Sept2002一一 !竺!兰!：!：!坚!三第23卷第5期利用找环去边法求最小生成树的算法探析姜洪溪，陈丹(襄樊学院电气信息工程系，湖北襄樊441053)摘要：文章在对连通网的特征进行分析的基础上，提出了种利用找环去边法求最小生成树的 算法，并对此算法作了定性的分析关键字：环秩：连通网；生成树；最小生成树中图分类号：TP39302文献标识码：A文章编号：10092854(2002)050066-03在多个城市(区域)问构建通信、交通、管道等网络时，很自然要考虑这样个问题：如何能在满足功 能需求的情况下以最小的代价来建设这个网络抽象地说，就是如何在一个连通网中找出其最小生成树的问 题1连通图的生成树下面介绍几个相关概念 (1)环秩：若无向连通图G中有n个顶点和Ill条边(记为G(n，m)，则其环秩为旷n+1 (2)生成树及其性质 生成树：个连通图G(n，m)的生成树是一个极小连通子图，它含有图中所有n个顶点，但只有足以构成一棵树的n一1条边生成树一般不唯一 性质：一棵有n个顶点的生成树有且仅有nl条边(即环秩为O)；如果一个图中有n个顶点和小于n一1条边则是非连通图；如果一个图中有n个顶点和多于n一1条边则一定有环 (3)最小生成树 最小生成树：在个有n个顶点的连通网中，其生成树中nl条边t权值之和最小的生成树称为此连通网的最小生成树在一个连通网中，其最小生成树也不一定唯一，但其最小生成树的权值之和一定唯一(为 一定值)由生成树的定义可以看出，个连通图G与其生成树T的差别在于图G中可能包含环而生成树T中不包 含任何环而在一个环中去掉一条边即可将此环破除，因此，我们可以用去掉图G中的环而又不破坏图G的 连通性的方法由图G构造其生成树T算法1(连通图的生成树构造算法)： 给定连通图G(n，m)，构造其生成树T： (1)令G为G；，置i为1； (2)若G。无环，则T=Gt，算法结束：否则(3)在G中找出任一环T；，并从t；中删去任一条边e；，称这剩余的图为G ； (4)i增加1，并返回到第(2)步 此算法的证明可参阅参考文献1在此算法中，图G。总是连通的，因为它是将图Gi中的一个环I i中收稿日期：20020118；修订日期：2002062l作者简介：姜洪溪(1968一)，男，湖北随州人，襄樊学院电气信息工程系副教授万方数据笫23卷第5期 2002年第5期删去任一条边e后形成的，而且图G的环秩比图G的环秩小1由于图G中的环的个数是有限的，因此对 某个j，我们一定能得到一个连通图G。，它包含图G中的所有结点但又不包含环于是根据生成树的定义， 图G就是生成树T从连通图G(n，m)变为生成树T(n，n一1)，删去的边数为旷(旷1)=m_n+1，即为图G的环秩因此，图G 的环秩是为了“弄破”G的所有环而必须从G中删去的边的最小数目，也即算法1中要重复执行的循环次数 从算法1可以看出，山于在将一个环中的边去掉时的选择可以不同，所得到的生成树T不是唯一的2连通网的最小生成树求连通网的最小生成树，方法与求连通图的生成树相类似，但最小生成树要求在产生的生成树中所有各 边权值的和为最小这样，我们有以下算法：算法2(连通网的最小生成树构造算法)：给定连通网G(n，Ill，w)，构造其最小生成树T： (1)令G为G一，置i为l； (2)若G；无环，则T=Gi，算法结束；否则(3)在G中找出任一环t；，并从t。中删去权值最大的一条边e，称这剩余的图为G。； (4)i增加1，并返回到第(2)步 算法1是对连通图的生成时进行构造，而算法2是对连通网(带权的连通图)的最小生成树进行构造比较算法1与算法2，可以得出树T是网G的生成树下面我们来证明由算法2得到的生成树T就是网G的最小生成树 定理1：从算法2得到的树T就是连通网G的最小生成树 分析：设连通网G(n，m，w)的各边e；的权值记为w(1im)，由算法2得到的树T(n，n_1)的边集E(T)=e，e”，e)，并假设Tf，(n，n-1)(其边繁记为E(T(1)为网G的一棵最小生成树，则这里只需证明树T与T。具有相同的权值即可 证明：若T=Tm则T为最小生成树；若T则在T中必至少存在一条边e；E(T)，使得e；不在E(T1)中，但e，e矿”，e；-都在E(T【J)中将边e添加到R中，则在TI，中必产生唯一的环C由于T是由算法2得到的一棵生成树，且TT)，则在环c中至少存在一条边e(ee，)=ili在E(T)中在树T。中添加e而删去e，令得到的新树为T，井i己W(T)为树T的各边权值之和，则W(T)=W(T。)+wtw 因为R是最小生成树，所以有W(T)w(TfJ)，因而w；mwO，即w；w而根据算法2，生成树T是住环C中去掉权值较大的若干边后生成的，至少去掉了边e而保留了e，因此，从生成树T的过程来看，在 环C中，wwi故有wi=w，进而w(T)-W(T。，)即树T也是一棵最小生成树注意到在生成树T中，T的边只有e。，e2， ，e，在E(1，)中，而在T中，T的边e， ，ee都在E(T) 中考虑到T和Tf)都是网G的最小生成树，对T与T也进行上述的过程，并反复进行这样的转换，可将最 小生成树TI，转换成树T”，其中边e，e2，一，e。都在E(T”)中，而权值没有任何增加(即W(T”)=w(TIJ)从 而T”也是一棵最小生成树，但E(T”)-E(T)，也即T”=T，故生成树T是连通网G的最小生成树3算法分析根据算法l，在利用算法2求最小生成树时，要去掉的边数也为环秩的大小IIrn+l_在一个连通网中， 环秩越小(即边越少)，算法2循环执行的次数越少因此，算法2时求边稀疏的连通网的最小生成树是一| 分适合的在算法2中，显然有两重循环：外循环的次数为要去掉的边数(m_n+1)，内循环为在连通网中找出一67万方数据姜洪溪，陈丹：利用找环去边法求最小生成树的算法探析个环找环算法只需将图的深度优先搜索算法作较小的修改，即在访问某一顶点后，若经过两个以上的顶点 后义回到该顶点，则说明有环存在在访问过程中，记录下当前权值最大的边及其权值，发现有环存在后， 去掉此边即可因此，当算法2应用于边稀疏的连通网时，其时间复杂度也是较低的本文在对连通网的特征进行分析的基础上，根据求生成树的算法1，提出了一种利用在连通网中查找环 的存在，并将此环中权值最大的边去掉来求最小生成树的算法2，并对此算法进行了证明在进一步对算法2作了定性的分析后，得出结论：本算法对求边稀疏的连通网的最小生成树是十分适合的参考文献：【11洪帆离散数学綦础【M1武汉：华中理T人学 版社，1995266-271【2】徐洁盘离散数学导论IMI北京：高等教育 版社，198363-77【3】严蔚敏数据结构(C语苦版)【M】北京：清华人学“I版礼，1997156159【4】卜朝瑞图论【M】北京：北京T业学院fl版利：，1985242262On Algorithm of Producing Minimum Cost Spanning Tree by Method of Seeking Cycles toRomove Its EdgeJIANG Hong-xi，CHAN Dan(Depanment of Electric&Information Engineering,Xiangfan University，Xiangfan 44 1 053China)Abstract：In this paperon the bases ofanalyzing the characteristics about Connected Network，an algorithm that produces the Minimum Cost Spanning Tree by using the method ofseeking the cycles in a Connected Network and removing an edge in each cycle is put forwardBy analyzing its basic properties it is shown th