最小生成树的算法

GOODBYEYT

引言：
求连通图的最小生成树是数据结构中讨论的一个重要问题．在现实生活中，经常遇到如何得到连通图的最小生成树，求最小生成树不仅是图论的基本问题之一 ,在实际工作中也有很重要的意义，,人们总想寻找最经济的方法将一个终端集合通过某种方式将其连接起来 ,比如将多个城市连为公路网络 ,要设计最短的公路路线;为了解决若干居民点供水问题 ,要设计最短的自来水管路线等.而避开这些问题的实际意义 ,抓住它们的数学本质 ,就表现为最小生成树的构造。下面将介绍几种最小生成树的算法。
一，用“破圈法”求全部最小生成树的算法
1 理论根据
1.1 约化原则
给定一无向连通图 G =（V,E）（ V 表示顶点，E表示边），其中 V={   ,  , ……   },E= {   ,  ,   ……   }对于 G 中的每条边 e   E都赋予权 （  ）>0，求生成树 T = （V,H），H   E，使生成树所有边权最小，此生成树称为最小生成树．
（1） 基本回路
将属于生成树 T 中的边称为树枝，树枝数为n -1，不属于生成树的边称为连枝．将任一连枝加到生成树上后都会形成一条回路．把这种回路称为基本回路，记为 。
基本回路是由 T 中的树枝和一条连枝构成的回路．
（2） 基本割集
设无向图 G 的割集 S （割集是把连通图分成两个分离部分的最少支路集合） ，若 S 中仅包含有T中的一条树枝，则称此割集为基本割集，记为 。
基本割集是集合中的元素只有一条是树枝，其他的为连枝．
（3） 等长变换
     设T=(V,H),为一棵生成树，e   H,   E,     H,当且仅当  ，也就是说e   ，则 =T {e,  }也是一棵生成树。当 = 时，这棵生成树叫做等长变换。
等长变换就是从基本回路中选取与树枝等权边，并与此树枝对换后形成的生成树．
根据以上定理得出2个结论：①若在某个回路C 中有一条唯一的最长边，则任何一棵最小生成树都不含这条边；②若在某个边 e 的割集中有一条唯一最短边，则每棵生成树中都必须含这条边．由上面结论可以得到唯一性：若图 G 中的生成树T = （V,H）是唯一的一棵最小生成树，当且仅当任意一连枝e   H,   E 都是其基本回路中唯一最长边，任意一条树边 e 都是其基本割集 中的唯一最短边．
由此在最小生成树不唯一的情况下，就可以得到一个约化的原则：假设已得到一棵最小生成树 。对于 中每一条树边e   H，若 e 是基本割集 中唯一的最短边，则每棵最小生成树中一定包含此边，则把此边取为固定边，并将此边的基本割集去掉。
对于每条连枝e   H,   E，若它是基本回路 中唯一最长边，则每棵生成树中都不会包含此条连枝，则将其消去．
约化原则是在最小生成树不唯一的情况下，从已经得到的一棵最小生成树 中选出其树枝是基本割集中唯一的最短边，则每一棵最小生成树中必含有此边，就取为固定边．在基本回路中若有一条唯一最长边，则每棵最小生成树都不含此条边，将其去掉．通过这样约化后再求最小生成树，计算量会大大下降．
1.2 全部最小生成树
设 是已求得的一棵最小生成树，在最小生成树不唯一的情况下，存在其他最小生成树 T，称T- 得到的边集的长度为距离（这里的长度是指集合中元素的个数）。
为了简单起见，设最小生成树 的边集为{   ,  ,   …… }，对于 的任何边集 ={   ,  ,   …… }（ ），则每棵最小生成树 T 与 的距离是一定的，或为1，或为2 ，或为 n -1．这样我们就可以按所有的最小生成树与 的距离来分类。
记 ={   ,  ,   …… }为所有的 — 即不含 的最小生成树的集合（可能为空）．对于其它的最小生成树T  而言， = —T为换出边， =T— 为入边， 中的边叫不动边．若 T 有 k 个换出边就说它与 的距离为 k．当 k=0 时为参考树本身。
当 k = 1 时，对任意的 ，有 。最小生成树 是用基本割集 的边 p 换出 的边 且边p 的权和边 的权相等。
当 k = 2时， 。在换入一条边后得到的生成树中再换入一条边，即换入两条边后得到的一棵最小生成树 。
以此递推下去，可建立如下关系： 此递推关系表示在换入k —1条边后得到的生成树中再换入一条边后得到的一棵最小生成树．用此递推关系，就可以求出全部的最小生成树。
2 算法
  选取一棵最小生成树 ，求出  的全部基本回路．对每一个基本回路去掉唯一最大边，约化所给的图．然后对应于  的每条树边，求出基本割集．若此树边也是基本割集中唯一最短边，则取其为固定边，并将此基本割集作上记号，求其他的最小生成树时，就不用考虑此割集了．其余的基本割集，应用递推关系，对应于递推式求出所有的换入边．对于距离为1的，每一个换入边对应着一棵最小生成树；对于距离为2 的每两个换入边也对应着一棵最小生成树；换入 k 条边，就对应着距离为 k 的最小生成树．以此类推就可以求出全部的
最小生成树．
求无向图 G 的全部最小生成树的算法如下．
（1） 求最小生成树  ．比较成熟的算法，在此就不做介绍．
（2） 求约化图算法 （去掉基本回路中的唯一最长边）
Step1 令 为连枝集合，j=1；
Step2 在  中加入连枝 ，形成一个基本回路，记为 ；
Step 3 若  是基本回路 中唯一最长边，则从图 G 中去掉 ；
Step4 j =j +1,若 j 不大于 b，则返回Step2；
Step5 输出经约化后的图 G。
（3 ）求固定边算法 （保留基本割集中唯一的最短边）
Step 1 令 E ={   ,  ,   …… }为最小生成树 的树枝集合，S = ， 为树枝 的基本割集，i=1;
Step 2 从约化后的图 G 中求出树枝 的基本割集 ；
Step3 若  是基本割集 S 中的唯一最短边，则将  取为固定边，并对 作记号；
   Step4 i 增加1, 若 i 不等于n, 则返回Step2．
（4） 求换入边算法（ 若基本割集中有记号，则为固定边，若没有记号，则从中求换入边）
Step1 设 H 为换入边的集合，F 为换出边的集合，初始 H、F 为空，i=1；
Step 2 若 的基本割集  = 中有记号，则  为固定边，执行Step 8；
Step3 若 的基本割集  中无记号，则  放入 F 中；
Step4 令 k= 1；
Step 5 若  ，且权 ， 放入H中；
Step6 k =k+ 1；
Step7 若 k < d （d 为  的长度，即 中元素的个数） 则返回Step5；
Step 8 i = i +1，若 i 小于或等于 n 1, 则返回Step 2．
（5） 求全部最小生成树算法 按距离从1到g 求全部最小生成树）
设 H = 为换入边的集合，F = 为换出边的集合．
Step 1 若 H 为空，则最小生成树是唯一，输出 ，算法结束．
( )
Step2 k =1,  =  , 输出  , （k 为距离） ；
Step3 j =k；
Step4 若 , 且权 ，则在 中用 代替 ，输出 （在已经换入 k 条边后的最小生成树中再换入 ，生成新的最小生成树）;
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) 所示的最小生成树称 ．
基本回路是由树枝和一条连枝组成的回路，由“破圈法”的思想，若此连枝是基本回路中的唯一最长边，则将此边去掉后得到约化图．无向图G的基本回路中的唯一最长边为：在基本回路①-②-⑦中有唯一最长边是<1，7>，其权为7，将其去掉；在基本回路③-④-⑦中有唯一最长边是<3，7>，其权为3，将其去掉；在基本回路⑤-⑥-⑦中有唯一最长边是<5，7>，其权为4，将其去掉；在基本回路①-②-⑦-⑥中有唯一最长边是<1，6>，其权为 8，将其去掉．去掉基本回路中的唯一最长的边后，形成如图1 (c) 所示的约化图．
对无向图 G 进行约化后，最小生成树  中各边的基本割集为：<1，2>：<1，2> ，<1，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>为唯一最短边，取为固定边，将此割集作上记号．
在  中，取为固定边的有 {<1，2>，<6，5>，<7，4>，<4，3> }．这样其他的最小生成树只能在 {<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 结论
本文在对连通图的特征进行分析的基础上，得出在某个基本回路 C 中有一条唯一的最长边，则任何一棵最小生成树都不含这条边，将此边从无向图 G 中去掉，对图进行约化；若在某个边 e的割集中有一条唯一最短边，则每棵生成树中都必须含这条边，则取为固定边．利用“破圈法”的思想去掉基本回路中的唯一最长边，保留基本割集中唯一最短边，对连通图进行约化，在约化图的基础上求全部最小生成树，计算量会大量地下降，算法的效率将大大地提高．
二，寻找最小生成树的补图算法
1        例谈补图算法思想
补图算法首先寻找最小生成树的补图 ,然后再求出该补图的补图即得最小生成树.（ 根据最小生成树的定义易知 ）在寻找最小生成树的补图的过程中 ,遵循以下 2 条原则:原则一 , 度为 1 的结点的关联边肯定不在补图中 ,删去不管;原则二 ,环上的最大权边一定在补图中 ,保留在补图中;循环利用上述原则 ,即可得到最小生成树的补图。
例如 ,已知一个连通的带权图 G （见图 1） ,要寻找其最小生成树. 由图 1知图 G 有 11 条边,8 个顶点,从而它的最小生成树的补图有且只有 4 条边. 算法步骤如下:
第 1 步:根据原则一 ,因为 deg （ ） =1,所以删去权 3 边,得图 2;
第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 的结点,去掉与之相关联的边,得新图记为  ;
2 ）把  赋予 G, 转 1）
3 ）把G 中所有环中的一条最大权边放入 GB 中,得新图  ;
4 ）记数GB 中边的条数,当 GB 中边的条数小于 m -（ n -1）时，把 赋予 G ,转 1），
若 GB 中边的条数等于 m - （n -1 ）时,跳出循环;
)
5）求出 GB 的补图,记为  ;  就是原图 G 的最小生成树。
3　算法的正确性定理及复杂度分析
定理 :上述算法给出的  是原图 G 的最小生成树.
     证明:由算法的过程知  是一棵含有 n -1 条边的连通图,所以一定是原图 G 的一棵生成树.
假设  =< V , E > 是原图 G 的最小生成树,则  中也含有 n -1 条边;再记  的边集为  ,若  =   则显然  =   ,即就是最小生成树;若   ，则必定存在一条边   ，而   ，把 加到 中 ,则在 上产生一个环 C,且在环 C 上至少有一条边 不在 中;下面在 中删去 ，加上 ,得新树 则  ( )= +  ,又因为 是最小生成树,所以   ,进而   .
而在环 C 上,若 > ,则在算法的第 3) 步知,  边将被放在 GB中 ,再经过算法的第 5 )步 ,则 不会在 中 ,即   ,矛盾.
所以 ,必有 = ,故 也是一棵最小生成树.
反复上述过程 ,最终将转化为 ,而权不变 ,从而知 就是图 G 的最小生成树.
该算法有 2 个优点 ,第 1 个在于该算法通过求最小生成树的补图来确定最小生成树 ,当面对的实际网络是稀疏图时 ,其时间复杂度较传统的方法要低;第 2 个在于该算法运用度为 1 的结点的关联边一定在最小生成树的事实 ,简化连通图 ,从而进一步降低了算法的复杂度.

wssl103050

不错不错哈

shaox

不错~~

qun3281

不错，基本的要掌握

心随意动

受教~~~~~~·········