《一种新的最小生成树算法》由会员分享，可在线阅读，更多相关《一种新的最小生成树算法（8页珍藏版）》请在金锄头文库上搜索。
1、一种新的最小生成树算法姓名：金鸿轩 班级：软件 13-6学号：132001062015-01-18一种新的最小生成树算法作者：金鸿轩辽宁工程技术大学软件学院，辽宁省葫芦岛市，125105摘 要：本文提出一种新的算法以完成加权连通图的最小生成树(minimum spanning tree,MST)。该算法具有以下优点：1，由于主要以排序为主，因此比较简单。2，算法复杂度与Boruvka 和 Prim（PFS，堆）算法是同一个数量级，在图的密度小于 1 的情况下，提出的算法比 Boruvka 和 Prim（PFS，堆）算法性能优越。3，即使在大型图中，内存不能一次读入全部数据，提出的算法在 Ste
2、p2 中只需扫描一次数据库就能完成，对系统要求较低。关键词：最小生成树；边顺生长；边逆生长；算法复杂度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 complexit
3、y 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 th
4、e data, the algorithm in Step2 scan a database, will be finished on the system requirements is low Closing date of draft ：2015.1.19Authors brief introduction ：jinhongxuan Communication contacts ：1.1. 引言对于一个随机加权无向图，寻找其最小生成树的问题有许多重要的应用，而且解决此问题的算 法至少从 1920 年就已经出现。然而，研究人员仍在寻求更好的方法。因为这个问题并没有到 完全的理解1 。经典的
5、 MST 算法其实现的效率大相径庭，这些算法（例如：Boruvka、Prim 算法等）在做运算时大都要求一次将数据读入内存中以做比较，如果处理的是大型图，内存没 办法在一次就把所有的数据读入时，这些算法将受到一定局限性（虽然也有一些片外排序的技 术，但其实现也不容易）。针对这个问题，本文提出一种新的算法以实现在无向连通图中寻找 最小生成树，基于分治法2 的思想，将主要的排序分为两部分，在每部分中的子运算只需求 读入内存很少的数据以做比较，而在算法复杂度和 Boruvka 和 Prim（PFS，堆）算法为同一 数量级，若图的密度小于 1 的话，本文提出的算法比 Boruvka 和 Prim（PF
6、S，堆）算法还更 优。 本文安排如下：在第二节中对 Boruvka, Prim 算法及本文算法进行了介绍；第三节对文章给 出的一个推论做了证明；在第四节中对算法的开销进行了推导并给出该算法的一个示例。第五 节对算法进行了评估并对全文进行了总结。2.2. 算法简介2.1.2.1. BoruvkaBoruvka 算法 Boruvka 算法由 Boruvka 于 1926 年提出（早于图论产生）。该算法为每个分量设置leade 用 DFS 在 m 时间内求出；在每次运算中 检查每条边一次以修正各分量的安全边权；第i 次 迭代每个分量大小至少为 2i ； 最多 logV 次迭代，总O(E logV )
7、。 以下是该算法的伪代码：2.22.2 PrimPrim 算法该算法由 Prim 提出，但事实上 Jarnik 于 1930 年更早提出。算法通过一系列不断扩张的子 树来构造一棵最小生成树。它从图的顶点集中任意选择一个单顶点作为序列中的初始子树，然 后每次加入该子树的安全边。下面是该算法的伪代码：2.32.3 本文提出算法输入：加权流通图 G， i j V V 表示 i V 到j V 的边， i j e . 表示i V 到j V 的边上的权输出： T E ，图 G 最小生成树的边集合Step1: 在每一个节点上寻找与之连接的最小边，这样会形成 K 棵树的森林，这些边的集合 为 1 E ，第 K
8、 棵树用该棵树的点集合表示 | K K K V V V i i ， 21 k V Step2: 在 Step1 中没有被选中的边的集合 E - 1 E 中，去掉森林中每一个树中的这些边( , ) | ( , ) , 1 E V V V V E E i j c Ki K j Ki K j = 。然后在剩余的边集合 E - 1 E - c E 寻找最的 k-1 条边，用集合 2 E 表示 Step3： 输出ET ， T 1 2 E = E E3.3. 一个推论的证明该推论相推论：在加权流通图中选择一个节点与之连接的权重最小的边所形成的集合是森林。 当于在形成过程中其每一个元素都是树。即等价于所选择
9、的这些边中不会形成回路。 3.13.1、两个定义：定义 1：K 个节点， K V ,V , ,V 1 2 L ,其形成边是按 1 2 k V V LV 称为“边顺生长(forward growth edge)”；如果其形成边是按k V1 V2 LV 称为“边逆生长(backwardgrowth edge)”。 定义 2：定义图 G的密度为： ( ) (V V ) f G E2 log=3.23.2、两个子推论：子推论 1：边顺生长的权重是逐渐变小，边逆生长的权重是逐渐变大的。子推论 2：同一个节 点与之相连最多只有一条边是顺生长的，而可以有多条边逆生长。由定义得两个子推论显然成 立。3.33.
10、3、证明（采用归纳法证明）3.3.1 考虑当 K3 时，节点 1 V ， 2 V ， 3 V ，设 1 V 最小的邻接边是 1 V 2 V ， 2 V 节点有两种情况：(a) 2 V 是边顺生长到 3 V 和(b) 2 V 是边逆生长到 3 V 。 （1）、在(a)中，假设如果 3 V 能边顺生长一条边到 1 V ，形成环，则由子推论 1 得 1,2 2,3 3,1 e e e ，与 1,2 e 是 1 V 与之连接的权重最小的边相矛盾，所以假设不成 立。假设如果 3 V 能边逆生长一条边到 1 V ，也即 1 V 边顺生长到 3 V （ 1 V 3 V ），由 子推论 2 得，1 V 已经是
11、一次边顺生长（ 1 V 2 V ），所以 1 V 上不会边顺生长到 3 V 形 成环。即在(a)中不会形成环。 （2）、在(b)中，由子推论 2 知，节点 1 V 、3 V 已不能再从这两个节点顺生长出边来，不 会再生成 1 V 3 V 边而形成环。 综（1）（2）所述当 K3 时不会形成环，即生成的边是树。 3.3.2、当 K3 时，考虑节点 1 V ， 2 V ， 3 V ， K V （1）、若边的形成是按 1 2 1 K V V L V 边顺生长，则按 3.3.1 中（1）的结论 知，无论 K1 V 是边顺生长到K V 还是 K1 V 是边逆生长到K V 都不会使K V 出现边 1 V
12、K V 而形成环。 （2）、若边的形成使按i V1 V2 LV （13 时不会形成环，即生成的边是树。 由 3.3.1、3.3.2 得推论成立。证毕。4.4. 算法的开销：4.14.1、在 Step1Step1 中的开销在Step1 结束时，若图中有 K（ 21 k V ）棵树，则选出的边为 V-K 条。令第 i 个节点有i x 条邻边，则选出这 V-K 条边需要比较的次数有(2E V)次：x E V x EViVii 1 2 , 21 1 因为 = = = 。4.24.2、在 Step2Step2 中的开销在 Step2 中，最坏情况下 = C E 为空集，即需要在剩余 E-(V-K)条边中
13、选出 K-1 条，按 一般逐个比较需要 = 1( )KE V K i 次 ， 采 用 快 速 排 序 一 类 需 要 ( )2 E (V K)log E V K 次。 下面介绍本文采用的方法： 先从 E-(V-K) 挑出 K-1 条边，其权为e i K i , = 1,2,L ，将这将这 K-1 条边权值排序， , 1, 2, i e = e i = LK ， max , 1,2, i e = e i = LK余下的（E-V-1）条边的 权为e , j = 1,2, E V 1 j for j=1; j1 时，算法的运算次数会略增加。图中(a)为一个无向加权连通图及其该图的 MST，左边为该图
14、各边的权重，其中颜色加 深部分为对应的 MST 边的权值。图(b)为本文法中的 Step1：在每个顶点找出与该顶点连接 权最小的边，形成森林，得到 1 E ；图(c)为算法中的 Step2：在 Step1 中没有被选中的边的 集合 E - 1 E 中，去掉森林中每一个树中c E 。然后在剩余的边集合 E - 1 E - c E 寻找最短的 k-1 条边。得到 2 E 。5.5.结论本文提出的算法主要有以下优点：1. 简单。主要以排序为主。2. 在算法复杂度上和 Boruvka 和 Prim（PFS，堆）算法是一个级别达到了E lgV 。在 f (G) 1 时，则算法比 Boruvka 和 Prim（PFS，堆）算法还较优。3. 即使在大型图中，在内存不能一次读入全部数据时，本算法 也能轻松处理。而且在 Step2 中只需扫描一次数据库就能完成。【参考文献】1 谭浩强C 语言程序设计北京：清华大学出版社，20002 严蔚敏，吴伟民数据结构(语言版)北京：清华大学出版社，19973 M.H.Alsuwaiyel 著，吴伟，方世昌等译算法设计技巧与分析北京：电子工业出版社，2004.8
