一种新的最小生成树算法.doc

一种新的最小生成树算法 姓名：金鸿轩 班级：软件13-6 学号 2015-01-18 一种新的最小生成树算法 作者：金鸿轩 辽宁工程技术大学软件学院，辽宁省葫芦岛市，125105 摘 要：本文提出一种新的算法以完成加权连通图的最小生成树(minimum spanning tree, MST)。该算法具有以下优点：1，由于主要以排序为主，因此比较简单。2，算法复杂度与 Boruvka 和Prim（PFS，堆）算法是同一个数量级，在图的密度小于1 的情况下，提出的算 法比Boruvka 和Prim（PFS，堆）算法性能优越。3，即使在大型图中，内存不能一次读入 全部数据，提出的算法在Step2 中只需扫描一次数据库就能完成，对系统要求较低。 关键词：最小生成树；边顺生长；边逆生长；算法复杂度 A new minimum spanning tree algorithm This paper presents a new algorithm to complete the weighted minimum spanning tree of connected graph ，The algorithm has the following advantages ：1，Because mainly the sorting, so simple 2The algorithm complexity and Boruvka and Prim (PFS, heap) algorithm is the same order of magnitude, the density of the diagram under the condition of less than 1, put forward to calculate Method than Boruvka and Prim algorithm (PFS, heap) superior performance.3Even in a large figure, memory cannot be read at a time All the data, the algorithm in Step2 scan a database, will be finished on the system requirements is low Closing date of draft ：2015.1.19 Authors brief introduction ：jinhongxuan Communication contacts ：985441540@ 1. 引言 对于一个随机加权无向图，寻找其最小生成树的问题有许多重要的应用，而且解决此问题的算法至少从1920 年就已经出现。然而，研究人员仍在寻求更好的方法。因为这个问题并没有到完全的理解[1] 。经典的MST 算法其实现的效率大相径庭，这些算法（例如：Boruvka、Prim 算法等）在做运算时大都要求一次将数据读入内存中以做比较，如果处理的是大型图，内存没办法在一次就把所有的数据读入时，这些算法将受到一定局限性（虽然也有一些片外排序的技术，但其实现也不容易）。针对这个问题，本文提出一种新的算法以实现在无向连通图中寻找最小生成树，基于分治法[2] 的思想，将主要的排序分为两部分，在每部分中的子运算只需求 读入内存很少的数据以做比较，而在算法复杂度和Boruvka 和Prim（PFS，堆）算法为同一 数量级，若图的密度小于1 的话，本文提出的算法比Boruvka 和Prim（PFS，堆）算法还更 优。 本文安排如下：在第二节中对Boruvka, Prim 算法及本文算法进行了介绍；第三节对文章给出的一个推论做了证明；在第四节中对算法的开销进行了推导并给出该算法的一个示例。第五节对算法进行了评估并对全文进行了总结。 2. 算法简介 2.1. Boruvka 算法 Boruvka 算法由Boruvka 于1926 年提出（早于图论产生）。该算法为每个分量设置’leade用DFS 在m 时间内求出；在每次运算中 检查每条边一次以修正各分量的安全边权；第i 次迭代每个分量大小至少为2i ； 最多logV 次迭代，总O(E logV )。 以下是该算法的伪代码： 2.2 Prim 算法 该算法由Prim 提出，但事实上Jarnik 于1930 年更早提出。算法通过一系列不断扩张的子树来构造一棵最小生成树。它从图的顶点集中任意选择一个单顶点作为序列中的初始子树，