《最小生成树的算法.docx》由会员分享，可在线阅读，更多相关《最小生成树的算法.docx（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、最小生成树的算法最小生成树的算法王洁引言：求连通图的最小生成树是数据构造中讨论的一个重要问题在现实生活中，经常碰到怎样得到连通图的最小生成树，求最小生成树不仅是图论的基本问题之一,在实际工作中也有很重要的意义，,人们总想寻找最经济的方法将一个终端集合通过某种方式将其连接起来,比方将多个城市连为公路网络,要设计最短的公路道路;为了解决若干居民点供水问题,要设计最短的自来水管道路等.而避开这些问题的实际意义,捉住它们的数学本质,就表现为最小生成树的构造。下面将介绍几种最小生成树的算法。一，用“破圈法求全部最小生成树的算法1理论根据1.1约化原则给定一无向连通图G=V,EV表示顶点，E表示边，其中V
2、=1v,2v,3vnv,E=1e,2e,3ene对于G中的每条边eE都赋予权ie0，求生成树T=V,H，H?E，使生成树所有边权最小，此生成树称为最小生成树1基本回路将属于生成树T中的边称为树枝，树枝数为n-1，不属于生成树的边称为连枝将任一连枝加到生成树上后都会构成一条回路把这种回路称为基本回路，记为()cfe。基本回路是由T中的树枝和一条连枝构成的回路2基本割集设无向图G的割集S割集是把连通图分成两个分离部分的最少支路集合，若S中仅包含有T中的一条树枝，则称此割集为基本割集，记为()Se。基本割集是集合中的元素只要一条是树枝，其他的为连枝3等长变换设T=(V,H),为一棵生成树，eH,eE
3、,e?H,当且仅当e()cfe，也就是讲e()Se，则T=Te,e也是一棵生成树。当()e=()e时，这棵生成树叫做等长变换。等长变换就是从基本回路中选取与树枝等权边，并与此树枝对换后构成的生成树根据以上定理得出2个结论：若在某个回路C中有一条唯一的最长边，则任何一棵最小生成树都不含这条边；若在某个边e的割集中有一条唯一最短边，则每棵生成树中都必须含这条边由上面结论能够得到唯一性：若图G中的生成树T=V,H是唯一的一棵最小生成树，当且仅当任意一连枝eH,eE都是其基本回路中唯一最长边，任意一条树边e都是其基本割集()Se中的唯一最短边由此在最小生成树不唯一的情况下，就能够得到一个约化的原则：假
4、设已得到一棵最小生成树0T。对于0T中每一条树边eH，若e是基本割集()Se中唯一的最短边，则每棵最小生成树中一定包含此边，则把此边取为固定边，并将此边的基本割集去掉。对于每条连枝eH,eE，若它是基本回路()cfe中唯一最长边，则每棵生成树中都不会包含此条连枝，则将其消去约化原则是在最小生成树不唯一的情况下，从已经得到的一棵最小生成树0T中选出其树枝是基本割集中唯一的最短边，则每一棵最小生成树中必含有此边，就取为固定边在基本回路中若有一条唯一最长边，则每棵最小生成树都不含此条边，将其去掉通过这样约化后再求最小生成树，计算量会大大下降1.2全部最小生成树设0T是已求得的一棵最小生成树，在最小生
5、成树不唯一的情况下，存在其他最小生成树T，称T-0T得到的边集的长度为距离这里的长度是指集合中元素的个数。为了简单起见，设最小生成树0T的边集为1e,2e,3e1ne-，对于0T的任何边集kH=1e,2e,3e1ke-11kn-，则每棵最小生成树T与0T的距离是一定的，或为1，或为2，或为n-1这样我们就能够按所有的最小生成树与0T的距离来分类。记1,2,iiTik=1e,2e,3e1ke-为所有的0TkH即不含kH的最小生成树的集合可能为空对于其它的最小生成树T1,2,iiTik而言，kH=0TT为换出边，kH=T0T为入边，0TT?中的边叫不动边若T有k个换出边就讲它与0T的距离为k当k=
6、0时为参考树本身。当k=1时，对任意的11in-，有10110,|(),()(),iiiiiTTeppSTpepe=。最小生成树1iT是用基本割集1iS的边p换出0T的边1ie且边p的权和边1ie的权相等。当k=2时，1,10,|()(),()(),iijiijijijijijijTTeppSTSTpepe=?=。在换入一条边后得到的生成树中再换入一条边，即换入两条边后得到的一棵最小生成树1,iijT。以此递推下去，可建立如下关系：1,2ik1,2ik11,2k-10kk,|()(),()(),iiiiikijiiiiTTeppSTSTpepe-=?=此递推关系表示在换入k1条边后得到的生成树
7、中再换入一条边后得到的一棵最小生成树用此递推关系，就能够求出全部的最小生成树。2算法选取一棵最小生成树0T，求出0T的全部基本回路对每一个基本回路去掉唯一最大边，约化所给的图然后对应于0T的每条树边，求出基本割集若此树边也是基本割集中唯一最短边，则取其为固定边，并将此基本割集作上记号，求其他的最小生成树时，就不用考虑此割集了其余的基本割集，应用递推关系，对应于递推式求出所有的换入边对于距离为1的，每一个换入边对应着一棵最小生成树；对于距离为2的每两个换入边也对应着一棵最小生成树；换入k条边，就对应着距离为k的最小生成树以此类推就能够求出全部的最小生成树求无向图G的全部最小生成树的算法如下1求最
8、小生成树0T比拟成熟的算法，在此就不做介绍2求约化图算法去掉基本回路中的唯一最长边Step1令123,pbpppp=为连枝集合，j=1；Step2在0T中参加连枝pj，构成一个基本回路，记为jcf；Step3若pj是基本回路jcf中唯一最长边，则从图G中去掉pj；Step4j=j+1,若j不大于b，则返回Step2；Step5输出经约化后的图G。3求固定边算法保留基本割集中唯一的最短边Step1令E=1e,2e,3e1ne-为最小生成树0T的树枝集合，S=121,nSSS-，iS为树枝ie的基本割集，i=1;Step2从约化后的图G中求出树枝ie的基本割集iS；Step3若ie是基本割集S中的
9、唯一最短边，则将ie取为固定边，并对iS作记号；Step4i增加1,若i不等于n,则返回Step24求换入边算法若基本割集中有记号，则为固定边，若没有记号，则从中求换入边Step1设H为换入边的集合，F为换出边的集合，初始H、F为空，i=1；Step2若ie的基本割集iS=12,dPPP中有记号，则ie为固定边，执行Step8；Step3若ie的基本割集iS中无记号，则ie放入F中；Step4令k=1；Step5若iekP，且权()(p)ike=，pk放入H中；Step6k=k+1；Step7若kStep8i=i+1，若i小于或等于n1,则返回Step25求全部最小生成树算法按距离从1到g求全
10、部最小生成树设H=12m,PPP为换入边的集合，F=12e,gee为换出边的集合Step1若H为空，则最小生成树是唯一，输出0T，算法结束()Step2k=1,11T=0T,输出0T,k为距离；Step3j=k；Step4若ekjjp,且权(e)kjjp=(，则在kjT中用jp代替kje，输出kjT在已经换入k条边后的最小生成树中再换入jp，生成新的最小生成树;Step5j=j+1，若j小于或等于m，重复上面的Step4；Step6k=k+1，若k小于或等于g，则返回Step3；Step7结束3应用举例例如图1(a)所示，无向图G是有权无向连通图，求全部最小生成树设由图1(a)得到一棵如图1(
11、b)所示的最小生成树称0T基本回路是由树枝和一条连枝组成的回路，由“破圈法的思想，若此连枝是基本回路中的唯一最长边，则将此边去掉后得到约化图无向图G的基本回路中的唯一最长边为：在基本回路-中有唯一最长边是，其权为7，将其去掉；在基本回路-中有唯一最长边是，其权为3，将其去掉；在基本回路-中有唯一最长边是，其权为4，将其去掉；在基本回路-中有唯一最长边是，其权为8，将其去掉去掉基本回路中的唯一最长的边后，构成如图1(c)所示的约化图对无向图G进行约化后，最小生成树0T中各边的基本割集为：，为唯一最短边，取为固定边，将此割集作上记号；：，；：，；：，为唯一最短边，取为固定边，将此割集作上记号；：，
12、为唯一最短边，取为固定边，将此割集作上记号；：，为唯一最短边，取为固定边，将此割集作上记号在0T中，取为固定边的有，这样其他的最小生成树只能在，和，这两个基本割集中选取了根据算法，得到换入边为，换出边为，当k=1时，换入一条边得到的最小生成树W()=w，用边换得到最小生成树a，如图1d所示；w=w，用换得到最小生成树b，如图1e所示；k=2时，用换后，再用换得到的最小生成树c，如图1f所示4结论本文在对连通图的特征进行分析的基础上，得出在某个基本回路C中有一条唯一的最长边，则任何一棵最小生成树都不含这条边，将此边从无向图G中去掉，对图进行约化；若在某个边e的割集中有一条唯一最短边，则每棵生成树
13、中都必须含这条边，则取为固定边利用“破圈法的思想去掉基本回路中的唯一最长边，保留基本割集中唯一最短边，对连通图进行约化，在约化图的基础上求全部最小生成树，计算量会大量地下降，算法的效率将大大地提高二，寻找最小生成树的补图算法1例谈补图算法思想补图算法首先寻找最小生成树的补图,然后再求出该补图的补图即得最小生成树.根据最小生成树的定义易知在寻找最小生成树的补图的经过中,遵循下面2条原则:原则一,度为1的结点的关联边肯定不在补图中,删去不管;原则二,环上的最大权边一定在补图中,保留在补图中;循环利用上述原则,即可得到最小生成树的补图。例如,已知一个连通的带权图G见图1,要寻找其最小生成树.由图1知
14、图G有11条边,8个顶点,进而它的最小生成树的补图有且只要4条边.算法步骤如下:V=1,所以删去权3边,得图2;第1步:根据原则一,由于deg1第2步:根据原则一,删去权10边得图3;第3步:根据原则二,把权12边放在补图GB图省略中得图4;第4步:根据原则一,删去权11边得图5;对产生的新图,依此循环运用2个原则处理,依次会把权12边,权9边,权7边,权6边放在补图GB图省略中,进而也就知最小生成树中含有权2边,权3边,权4边,权5边,权8边,权10边,权11边,如图6所示.2算法描绘设G=是一具有n个结点m条边的连通有权图,构造G的最小生成树:1判定图G能否有度为1的结点,若无度为1的结点
15、,转3;若有度为1的结点,去掉与之相关联的边,得新图记为1G;2把1G赋予G,转13把G中所有环中的一条最大权边放入GB中,得新图1G;4记数GB中边的条数,当GB中边的条数小于m-n-1时，把1G赋予G,转1，若GB中边的条数等于m-n-1时,跳出循环;)5求出GB的补图,记为rT;rT就是原图G的最小生成树。3算法的正确性定理及复杂度分析定理:上述算法给出的rT是原图G的最小生成树.证实:由算法的经过知rT是一棵含有n-1条边的连通图,所以一定是原图G的一棵生成树.假设0T=是原图G的最小生成树,则0E中也含有n-1条边;再记rT的边集为rE,若rE=0E则显然rT=0T,即就是最小生成树
16、;若rE0E，则必定存在一条边ierE，而ie?rE，把ie加到0E中,则在0T上产生一个环C,且在环C上至少有一条边e不在rE中;下面在0T中删去e，加上ie,得新树T则(T)=0()T+()ife()fe-,又由于0T是最小生成树,所以()T0()T,进而()ife()fe.而在环C上,若()ife()fe,则在算法的第3)步知,ie边将被放在GB中,再经过算法的第5)步,则ie不会在rT中,即ie?rE,矛盾.所以,必有()ife=()fe,故T也是一棵最小生成树.反复上述经过,最终将转化为rT,而权不变,进而知rT就是图G的最小生成树.该算法有2个优点,第1个在于该算法通过求最小生成树的补图来确定最小生成树,当面对的实际网络是稀疏图时,其时间复杂度较传统的方法要低;第2个在于该算法运用度为1的结点的关联边一定在最小生成树的事实,简化连通图,进而进一步降低了算法的复杂度.