资源描述：
《集成gis的电信收入保障系统模型研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、集成GIS的电信收入保障系统模型研究//.paper.edu.cn-1-一种新的最小生成树算法罗竣友，尤众，赵军辉澳门科技大学，广东珠海(519000)摘要：本文提出一种新的算法以完成加权连通图的最小生成树(minimumspanningtree,MST)。该算法具有以下优点：1，由于主要以排序为主，因此比较简单。2，算法复杂度与Boruvka和Prim（PFS，堆）算法是同一个数量级，在图的密度小于1的情况下，提出的算法比Boruvka和Prim（PFS，堆）算法性能优越。3，即使在大型图中，内存不能一次读入全部数据，提出的算法在Step2中只需扫描
2、一次数据库就能完成，对系统要求较低。关键词：最小生成树；边顺生长；边逆生长；算法复杂度1.引言对于一个随机加权无向图，寻找其最小生成树的问题有许多重要的应用，而且解决此问题的算法至少从1920年就已经出现。然而，研究人员仍在寻求更好的方法。因为这个问题并没有得到完全的理解[1]。经典的MST算法其实现的效率大相径庭，这些算法（例如：Boruvka、Prim算法等）在做运算时大都要求一次将数据读入内存中以做比较，如果处理的是大型图，内存没办法在一次就把所有的数据读入时，这些算法将受到一定局限性（虽然也有一些片外排序的技术，但其实现也不容易）。针对这个问题
3、，本文提出一种新的算法以实现在无向连通图中寻找最小生成树，基于分治法[2]的思想，将主要的排序分为两部分，在每部分中的子运算只需求读入内存很少的数据以做比较，而在算法复杂度和Boruvka和Prim（PFS，堆）算法为同一数量级，若图的密度小于1的话，本文提出的算法比Boruvka和Prim（PFS，堆）算法还更优。本文安排如下：在第二节中对Boruvka,Prim算法及本文算法进行了介绍；第三节对文章给出的一个推论做了证明；在第四节中对算法的开销进行了推导并给出该算法的一个示例。第五节对算法进行了评估并对全文进行了总结。2.算法简介2.1.Boruv
4、ka算法Boruvka算法由Boruvka于1926年提出（早于图论产生）[4]。该算法为每个分量设置’leader’,用DFS在m时间内求出；在每次运算中检查每条边一次以修正各分量的安全边权；第i次迭代每个分量大小至少为2i；最多logV次迭代，总(log)OEV。以下是该算法的伪代码：//.paper.edu.cn-2-(,):BORUVKAVE??F=(V,)whileFhasmorethanonecomponentchooseleadersusingDFSFindSafeEdges(V,E)foreachleadervaddsafe(v)toF
5、←∞∈←←≠←FindSfeEdges(V,E):foreachleadervsafe(v)foreachedge(u,v)Euleader(u)vleader(v)ifuvifw(u,v)<w(safe(u))safe(u)(u,v)ifw(u,v)<w(safe(v))s←afe(v)(u,v)2.2Prim算法该算法由Prim提出，但事实上Jarnik于1930年更早提出。算法通过一系列不断扩张的子树来构造一棵最小生成树。它从图的顶点集中任意选择一个单顶点作为序列中的初始子树，然后每次加入该子树的安全边。下面是该算法的伪代码：0,G{
6、}11(,)(,),vtoVvuvuvu??????←←Φ←??=TTTTTPrim(G)//Prim//G=<V,E>//EV//EforidoVV-V算法构造最小生成树的算法输入：加权连通图输出：组成的最小生成树的边的集合可以用任意顶点来初始化树的顶点集合在所有的边中，求权重最小的边e使得在中，而在中{}u????←∪←∪TTTTTVVEEreturnEe2.3本文提出算法输入：加权流通图G＝<V,E>，jiVV表示iV到jV的边，jie.表示iV到jV的边上的权输出：TE，图G最小生成树的边集合Step1:在每一个节点上寻
7、找与之连接的最小边，这样会形成K棵树的森林，这些边的集合为1E，第K棵树用该棵树的点集合表示}
8、{KKKVVVii∈，????????????≤≤21VkStep2:在Step1中没有被选中的边的集合{E-1E}中，去掉森林中每一个树中的这些边}},{),(
9、),{(1jiEEVVVVEjijiKKKKc≠??∈=。然后在剩余的边集合{E-1E-cE}寻找最//.paper.edu.cn-3-短的k-1条边，用集合2E表示Step3：输出TE，12TEEE=∪3.一个推论的证明推论：在加权流通图中选择一个节点与之连接的权重最小的边所形成的集合是森林。该
10、推论相当于在形成过程中其每一个元素都是树。即等价于所选择的这些边中不会形成回路。3.1、两个定
