最小生成树的算法

最小生成树的算法 王洁 求连通图的最小生成树是数据结构中讨论的一个重要问题．在现实生活中，经常遇到如何得 到连通图的最小生成树，求最小生成树不仅是图论的基本问题之一 ,在实际工作中也有很重要的意义，,人们总想寻找最经济的方法将一个终端集合通过某种方式将其连接起来 ,比如将多个城市连为公路网络 ,要设计最短的公路路线;为了解决若干居民点供水问题 ,要设计最短的自来水管路线等.而避开这些问题的实际意义 ,抓住它们的 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 本质 ,就表现为最小生成树的构造。下面将介绍几种最小生成树的算法。 1 1.1 约化原则 给定一无向连通图 G =（V,E）（ V 表示顶点，E表示边），其中 V={ vvv , ,„„ 123 ,veeeee, },E= { , , „„ }对于 G 中的每条边 e E都赋予权（ ）>0，求n123ni 生成树 T = （V,H），H E，使生成树所有边权最小，此生成树称为最小生成树． , （1） 基本回路 将属于生成树 T 中的边称为树枝，树枝数为n -1，不属于生成树的边称为连枝．将任 一连枝加到生成树上后都会形成一条回路．把这种回路称为基本回路，记为cfe()。 基本回路是由 T 中的树枝和一条连枝构成的回路． （2） 基本割集 设无向图 G 的割集 S （割集是把连通图分成两个分离部分的最少支路集合） ，若 S 中仅包含有T中的一条树枝，则称此割集为基本割集，记为。 Se() 基本割集是集合中的元素只有一条是树枝，其他的为连枝． （3） 等长变换 ''' 设T=(V,H),为一棵生成树，e , H, e, E, e H,当且仅当e,cfe()，也就是说, '''e ,,()e，则=T{e, e}也是一棵生成树。当,()e=时，这棵生成树叫做等长变Se()T, 换。 等长变换就是从基本回路中选取与树枝等权边，并与此树枝对换后形成的生成树． 根据以上定理得出2个结论：?若在某个回路C 中有一条唯一的最长边，则任何一棵 最小生成树都不含这条边；?若在某个边 e 的割集中有一条唯一最短边，则每棵生成树中 都必须含这条边．由上面结论可以得到唯一性：若图 G 中的生成树T = （V,H）是唯一的 一棵最小生成树，当且仅当任意一连枝e ',e, H, E 都是其基本回路中唯一最长边，任 意一条树边 e 都是其基本割集Se()中的唯一最短边． TT,。对于中每一条树边e H，若 e 是基本割集中唯一的最短边，则每Se()00 由此在最小生成树不唯一的情况下，就可以得到一个约化的原则：假设已得到一棵最棵最小生成树中一定包含此边，则把此边取为固定边，并将此边的基本割集去掉。 小生成树'对于每条连枝e , H, E，若它是基本回路中唯一最长边，则每棵生成树e,cfe() 中都不会包含此条连枝，则将其消去． 约化原则是在最小生成树不唯一的情况下，从已经得到的一棵最小生成树T中选出其0树枝是基本割集中唯一的最短边，则每一棵最小生成树中必含有此边，就取为固定边．在基 本回路中若有一条唯一最长边，则每棵最小生成树都不含此条边，将其去掉．通过这样约化 后再求最小生成树，计算量会大大下降． 1.2 全部最小生成树 设T是已求得的一棵最小生成树，在最小生成树不唯一的情况下，存在其他最小生成0 树 T，称T-T得到的边集的长度为距离（这里的长度是指集合中元素的个数）。 0 为了简单起见，设最小生成树TeeeeT的边集为{ , , „„}，对于的任何0123n,10边集HeeeeT={ , , „„}（），则每棵最小生成树 T 与的距离是11,,,knk123k,10一定的，或为1，或为2 ，或为 n -1．这样我们就可以按所有的最小生成树与T的距离来0分类。 记TeeeeTHH={ , , „„}为所有的—即不含的最小生成树的ii1,2,……ik123k,10kk集合（可能为空）．对于其它的最小生成树TTHTH,而言，=—T为换出边，=Tii1,2,……ikk0k—TTT,T为入边，中的边叫不动边．若 T 有 k 个换出边就说它与的距离为 k．当 k=0 000时为参考树本身。 当 k = 1 时，对任意的，有11,,,inTTeppSTpepe,,,,,{{,}|(),()(),},,TS。最小生成树是用基本割集的iiiii1011011i1i1边 p 换出Tee的边且边p 的权和边的权相等。 0i1i1 当 k = 2时，TTeppSTSTpepe,,,,,,{{,}|()(),()(),},,。在换iijiijijijijijij1,10 入一条边后得到的生成树中再换入一条边，即换入两条边后得到的一棵最小生成树T。 iij1, 以此递推下去，可建立如下关系： TTeppSTSTpepe,,,,,,{{,}|()(),()(),},,此递iiiiikijiiii1,2ik1,2ik11,2k-10kk………………, 推关系表示在换入k —1条边后得到的生成树中再换入一条边后得到的一棵最小生成树．用 此递推关系，就可以求出全部的最小生成树。 TT 选取一棵最小生成树，求出 的全部基本回路．对每一个基本回路去掉唯一最大边，002 约化所给的图．然后对应于T 的每条树边，求出基本割集．若此树边也是基本割集中唯一0 最短边，则取其为固定边，并将此基本割集作上记号，求其他的最小生成树时，就不用考虑 此割集了．其余的基本割集，应用递推关系，对应于递推式求出所有的换入边．对于距离为 1的，每一个换入边对应着一棵最小生成树；对于距离为2 的每两个换入边也对应着一棵最小生成树；换入 k 条边，就对应着距离为 k 的最小生成树．以此类推就可以求出全部的 最小生成树． 求无向图 G 的全部最小生成树的算法如下． （1） 求最小生成树T ．比较成熟的算法，在此就不做介绍． 0 （2） 求约化图算法 （去掉基本回路中的唯一最长边） Step1 令pppp,{,,,p}……为连枝集合，j=1； 123b Step2 在pcfT 中加入连枝，形成一个基本回路，记为； jj0 Step 3 若pcfp 是基本回路中唯一最长边，则从图 G 中去掉； jjj Step4 j =j +1,若 j 不大于 b，则返回Step2； Step5 输出经约化后的图 G。 （3 ）求固定边算法 （保留基本割集中唯一的最短边） Step 1 令 E ={ eeeeT , , „„}为最小生成树的树枝集合，S 123n,10={,,}SSS……Se，为树枝的基本割集，i=1; 121n,ii Step 2 从约化后的图 G 中求出树枝eS的基本割集； ii Step3 若eeS 是基本割集 S 中的唯一最短边，则将 取为固定边，并对作记号； iii Step4 i 增加1, 若 i 不等于n, 则返回Step2． （4） 求换入边算法（ 若基本割集中有记号，则为固定边，若没有记号，则从中求换入边） Step1 设 H 为换入边的集合，F 为换出边的集合，初始 H、F 为空，i=1； Step 2 若eS{,,}PP……Pe的基本割集 =中有记号，则 为固定边，执行Step 8； ii12di Step3 若eSe的基本割集 中无记号，则 放入 F 中； iii Step4 令 k= 1； Step 5 若e,P,,()(p)e,p，且权，放入H中； ikikk Step6 k =k+ 1； Step7 若 k < d （d 为SS 的长度，即中元素的个数） 则返回Step5； ii Step 8 i = i +1，若 i 小于或等于 n 1, 则返回Step 2． {e,,}e……e{,,}PPP……为换入边的集合，F =为换出边的集合． 12g12m （5） 求全部最小生成树算法 按距离从1到g 求全部最小生成树） Step 1 若 H 为空，则最小生成树是唯一，输出T，算法结束． 设 H =0 ( ) Step2 k =1, TTT= , 输出 , （k 为距离） ； 1100 Step3 j =k； Step4 若e,p,,(e)）=(pTpeT, 且权，则在中用代替，输出（在已经换kjjkjjkjjkjkj入 k 条边后的最小生成树中再换入p，生成新的最小生成树）; j Step 5 j = j +1，若 j小于或等于m，重复上面的Step 4； Step 6 k = k + 1，若 k 小于或等于 g，则返回Step 3； Step7 结束． 3 例 如图1 (a) 所示，无向图 G 是有权无向连通图，求全部最小生成树． 设由图 1 (a) 得到一棵如图1( b) 所示的最小生成树称T． 0 基本回路是由树枝和一条连枝组成的回路，由“破圈法”的思想，若此连枝是基本回路 中的唯一最长边，则将此边去掉后得到约化图．无向图G的基本回路中的唯一最长边为： 在基本回路?-?-?中有唯一最长边是<1，7>，其权为7，将其去掉；在基本回路?-?-?中有唯一最长边是<3，7>，其权为3，将其去掉；在基本回路?-?-?中有唯一最长边是<5，7>，其权为4，将其去掉；在基本回路?-?-?-?中有唯一最长边是<1，6>，其权为 8，将其去掉．去掉基本回路中的唯一最长的边后，形成如图1 (c) 所示的约化图． 对无向图 G 进行约化后，最小生成树T 中各边的基本割集为：<1，2>：<1，2> ，<1，0 2>为唯一最短边，取为固定边，将此割集作上记号；<2，7>：{<2，7>，<2，3> }；<6，7>：{<6，7>，<5，4>}；<6，5>：{<6，5>，<5，4>}，<6，5>为唯一最短边，取为固定边，将 此割集作上记号；<4，3>：{<4，3>，<2，3>} ，<4，3>为唯一最短边，取为固定边，将此 割集作上记号；<7，4>：{<7，4>，<2，3>，<5，4>} ，<7，4>为唯一最短边，取为固定 边，将此割集作上记号． 在T 中，取为固定边的有 {<1，2>，<6，5>，<7，4>，<4，3> }．这样其他的最小生0 成树只能在 {<2，7>，<2，3>} 和{ <6，7>，<5，4> }这两个基本割集中选取了．根据算法， 得到换入边为 {<2，3>，<5，4>} ，换出边为 {<2，7>，<6，7>} ． 当 k = 1 时，换入一条边得到的最小生成树．W(<2，7> )=w（<2，3>），用边<2，3>换<2，7>得到最小生成树a，如图1（ d） 所示；w （<6，7>） =w （<5，4>），用<5，4>换<6，7>得到最小生成树b，如图1 （e ）所示； k =2 时，用<2，3>换<2，7>后，再用<5，4>换<6，7>得到的最小生成树c，如图1 （f） 所示． 4 本文在对连通图的特征进行 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 的基础上，得出在某个基本回路 C 中有一条唯一的最长边，则任何一棵最小生成树都不含这条边，将此边从无向图 G 中去掉，对图进行约化；若 在某个边 e的割集中有一条唯一最短边，则每棵生成树中都必须含这条边，则取为固定 边．利用“破圈法”的思想去掉基本回路中的唯一最长边，保留基本割集中唯一最短边，对 连通图进行约化，在约化图的基础上求全部最小生成树，计算量会大量地下降，算法的效率 将大大地提高． 1 补图算法首先寻找最小生成树的补图 ,然后再求出该补图的补图即得最小生成树（. 根据最小生成树的定义易知 ）在寻找最小生成树的补图的过程中 ,遵循以下 2 条原则:原则一 , 度为 1 的结点的关联边肯定不在补图中 ,删去不管;原则二 ,环上的最大权边一定在补 图中 ,保留在补图中;循环利用上述原则 ,即可得到最小生成树的补图。 例如 ,已知一个连通的带权图 G （见图 1） ,要寻找其最小生成树. 由图 1知图 G 有 11 条边,8 个顶点,从而它的最小生成树的补图有且只有 4 条边. 算法步骤如下: 第 1 步:根据原则一 ,因为 deg （V） =1,所以删去权 3 边,得图 2; 1 第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 =< V , E, f >是一具有 n 个结点 m 条边的连通有权图,构造 G的最小生成树: 1 ）判断图 G 是否有度为 1 的结点,若无度为 1 的结点,转 3） ;若有度为 1 的结点,去掉 G ; 与之相关联的边,得新图记为1 2 ）把G 赋予 G, 转 1） 1 3 ）把G 中所有环中的一条最大权边放入 GB 中,得新图G ; 1 4 ）记数GB 中边的条数,当 GB 中边的条数小于 m -（ n -1）时，把G赋予 G ,转 1）， 1若 GB 中边的条数等于 m - （n -1 ）时,跳出循环; ) 5）求出 GB 的补图,记为TT ; 就是原图 G 的最小生成树。 rr T 是原图 G 的最小生成树. r 3 证明:由算法的过程知T 是一棵含有 n -1 条边的连通图,所以一定是原图 G 的一棵r 定理 :上述算法给出的 生成树. 假设TET =< V , E > 是原图 G 的最小生成树,则 中也含有 n -1 条边;再记 的边00r集为,EEETTEE ,若 = 则显然 = ,即就是最小生成树;若，则必定存在一条边rr0r0r0 'e,EeEeET，而，把加到中 ,则在上产生一个环 C,且在环 C 上至少有一条边e,iriri00 '''',ETe,()Tfe(),fe()不在中;下面在中删去e，加上,得新树则 ()=+,又因为TTr0i0i ''T,()T,()Tfe()fe()是最小生成树,所以,进而. ,,00i '而在环 C 上,若fe()fe()e>,则在算法的第 3) 步知, 边将被放在 GB中 ,再经ii过算法的第 5 )步 ,则eTeE不会在中 ,即,矛盾. ,irir ''所以 ,必有fe()fe()=,故也是一棵最小生成树. Ti 反复上述过程 ,最终将转化为TT,而权不变 ,从而知就是图 G 的最小生成树. rr 该算法有 2 个优点 ,第 1 个在于该算法通过求最小生成树的补图来确定最小生 成树 ,当面对的实际网络是稀疏图时 ,其时间复杂度较传统的方法要低;第 2 个在于该算法运用度为 1 的结点的关联边一定在最小生成树的事实 ,简化连通图 ,从而进一步降低了算法的复杂度.