集成GIS的电信收入保障系统模型研究.docVIP

集成GIS的电信收入保障系统模型研究 //.paper.edu.cn - 1 - 一种新的最小生成树算法 罗竣友，尤众，赵军辉 澳门科技大学，广东珠海 (519000) 摘 要：本文提出一种新的算法以完成加权连通图的最小生成树(minimum spanning tree, MST)。该算法具有以下优点：1，由于主要以排序为主，因此比较简单。2，算法复杂度与 Boruvka和 Prim（PFS，堆）算法是同一个数量级，在图的密度小于 1的情况下，提出的算 法比 Boruvka 和 Prim（PFS，堆）算法性能优越。3，即使在大型图中，内存不能一次读入 全部数据，提出的算法在 Step2中只需扫描一次数据库就能完成，对系统要求较低。 关键词：最小生成树；边顺生长；边逆生长；算法复杂度 1. 引言 对于一个随机加权无向图，寻找其最小生成树的问题有许多重要的应用，而且解决此问 题的算法至少从 1920 年就已经出现。然而，研究人员仍在寻求更好的方法。因为这个问题 并没有得到完全的理解 [1] 。 经典的 MST 算法其实现的效率大相径庭，这些算法（例如：Boruvka、Prim 算法等） 在做运算时大都要求一次将数据读入内存中以做比较，如果处理的是大型图，内存没办法在 一次就把所有的数据读入时，这些算法将受到一定局限性（虽然也有一些片外排序的技术， 但其实现也不容易）。针对这个问题，本文提出一种新的算法以实现在无向连通图中寻找最 小生成树，基于分治法 [2]的思想，将主要的排序分为两部分，在每部分中的子运算只需求 读入内存很少的数据以做比较，而在算法复杂度和 Boruvka 和 Prim（PFS，堆）算法为同一 数量级，若图的密度小于 1 的话，本文提出的算法比 Boruvka 和 Prim（PFS，堆）算法还更 优。 本文安排如下：在第二节中对 Boruvka, Prim 算法及本文算法进行了介绍；第三节对文 章给出的一个推论做了证明；在第四节中对算法的开销进行了推导并给出该算法的一个示 例。第五节对算法进行了评估并对全文进行了总结。 2. 算法简介 2.1. Boruvka 算法 Boruvka 算法由 Boruvka 于 1926 年提出（早于图论产生） [4]。 该算法为每个分量设置’leader’,用 DFS 在 m 时间内求出；在每次运算中 检查每条 边一次以修正各分量的安全边权；第 i 次迭代每个分量大小至少为 2i ； 最多 logV 次迭代， 总 ( log )O E V 。 以下是该算法的伪代码： //.paper.edu.cn - 2 - ( , ) :BORUVKA V E ?? F=(V, ) while F has more than one component choose leaders using DFS FindSafeEdges(V,E) for each leader v add safe(v) to F ←∞ ∈ ← ← ≠ ← FindSfeEdges(V,E): for each leader v safe(v) for each edge (u,v) E u leader(u) v leader(v) if u v if w(u,v)lt;w(safe(u)) safe(u) (u,v) if w(u,v)lt;w(safe(v)) s ←afe(v) (u,v) 2.2 Prim 算法 该算法由 Prim 提出，但事实上 Jarnik 于 1930 年更早提出。 算法通过一系列不断扩张的子树来构造一棵最小生成树。它从图的顶点集中任意选择 一个单顶点作为序列中的初始子树，然后每次加入该子树的安全边。下面是该算法的伪代码： 0 , G { } 1 1 ( , ) ( , ), v to V v u v u v u ?? ?? ?? ← ←Φ ← ?? = T T T T T Prim(G) // Prim // G =lt; V,Egt; // E V // E for i do V V-V 算法 构造最小生成树的 算法 输入：加权连通图 输出： 组成 的最小生成树的边的集合 可以用任意顶点来初始化树的顶点集合 在所有的边 中，求权重最小的边e 使得 在 中，而 在 中 { }u?? ?? ← ∪ ← ∪ T T T T T V V E E return E e