资源描述：
《最小生成树的算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、最小生成树的算法摘要：最小生成树的算法.王洁.引言：.求连通图的最小生成树是数据结构中讨论的一个重要问题．在现实生活中，经常遇到如何得到连通图的最小生成树，求最小生成树不仅是图论...关键词：算法,数据结构类别：专题技术来源：牛档搜索（Niudown.COM） 本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）
2、不对其付相应的法律责任！最小生成树的算法王洁引言：求连通图的最小生成树是数据结构中讨论的一个重要问题．在现实生活中，经常遇到如何得到连通图的最小生成树，求最小生成树不仅是图论的基本问题之一,在实际工作中也有很重要的意义，,人们总想寻找最经济的方法将一个终端集合通过某种方式将其连接起来,比如将多个城市连为公路网络,要设计最短的公路路线;为了解决若干居民点供水问题,要设计最短的自来水管路线等.而避开这些问题的实际意义,抓住它们的数学本质,就表现为最小生成树的构造。下面将介绍几种最小生成树的算法。一，用“破
3、圈法”求全部最小生成树的算法1理论根据1.1约化原则给定一无向连通图G=（V,E）（V表示顶点，E表示边），其中V={,,……},E={,,……}对于G中的每条边eE都赋予权（）>0，求生成树T=（V,H），HE，使生成树所有边权最小，此生成树称为最小生成树．（1）基本回路将属于生成树T中的边称为树枝，树枝数为n-1，不属于生成树的边称为连枝．将任一连枝加到生成树上后都会形成一条回路．把这种回路称为基本回路，记为。基本回路是由T中的树枝和一条连枝构成的回路．（2）基本割集设无向图G的割集S（割集是把连
4、通图分成两个分离部分的最少支路集合），若S中仅包含有T中的一条树枝，则称此割集为基本割集，记为。基本割集是集合中的元素只有一条是树枝，其他的为连枝．（3）等长变换设T=(V,H),为一棵生成树，eH,E,H,当且仅当，也就是说e，则=T{e,}也是一棵生成树。当=时，这棵生成树叫做等长变换。等长变换就是从基本回路中选取与树枝等权边，并与此树枝对换后形成的生成树．根据以上定理得出2个结论：①若在某个回路C中有一条唯一的最长边，则任何一棵最小生成树都不含这条边；②若在某个边e的割集中有一条唯一最短边，则每
5、棵生成树中都必须含这条边．由上面结论可以得到唯一性：若图G中的生成树T=（V,H）是唯一的一棵最小生成树，当且仅当任意一连枝eH,E都是其基本回路中唯一最长边，任意一条树边e都是其基本割集中的唯一最短边．由此在最小生成树不唯一的情况下，就可以得到一个约化的原则：假设已得到一棵最小生成树。对于中每一条树边eH，若e是基本割集中唯一的最短边，则每棵最小生成树中一定包含此边，则把此边取为固定边，并将此边的基本割集去掉。对于每条连枝eH,E，若它是基本回路中唯一最长边，则每棵生成树中都不会包含此条连枝，则将其
6、消去．约化原则是在最小生成树不唯一的情况下，从已经得到的一棵最小生成树中选出其树枝是基本割集中唯一的最短边，则每一棵最小生成树中必含有此边，就取为固定边．在基本回路中若有一条唯一最长边，则每棵最小生成树都不含此条边，将其去掉．通过这样约化后再求最小生成树，计算量会大大下降．1.2全部最小生成树设是已求得的一棵最小生成树，在最小生成树不唯一的情况下，存在其他最小生成树T，称T-得到的边集的长度为距离（这里的长度是指集合中元素的个数）。为了简单起见，设最小生成树的边集为{,,……}，对于的任何边集={,,
7、……}（），则每棵最小生成树T与的距离是一定的，或为1，或为2，或为n-1．这样我们就可以按所有的最小生成树与的距离来分类。记={,,……}为所有的—即不含的最小生成树的集合（可能为空）．对于其它的最小生成树T而言，=—T为换出边，=T—为入边，中的边叫不动边．若T有k个换出边就说它与的距离为k．当k=0时为参考树本身。当k=1时，对任意的，有。最小生成树是用基本割集的边p换出的边且边p的权和边的权相等。当k=2时，。在换入一条边后得到的生成树中再换入一条边，即换入两条边后得到的一棵最小生成树。以此递
8、推下去，可建立如下关系：此递推关系表示在换入k—1条边后得到的生成树中再换入一条边后得到的一棵最小生成树．用此递推关系，就可以求出全部的最小生成树。2算法选取一棵最小生成树，求出的全部基本回路．对每一个基本回路去掉唯一最大边，约化所给的图．然后对应于的每条树边，求出基本割集．若此树边也是基本割集中唯一最短边，则取其为固定边，并将此基本割集作上记号，求其他的最小生成树时，就不用考虑此割集了．其余的基本割集，应用递推关系，对应于递推式求出所有的换入边．对于距
