最小生成树算法及其应用【文献综述】.doc

1、毕业设计文献综述 信息与计算科学 最小生成树算法及其应用 最小生成树 (minimum spanning tree,MST)是计算机学科中一重要内容 , 其算法也是重要的计算方法 , 是现代科学中比较热门的研究方向 . 树是图论的重要内容 , 在计算机科学技术 , 特别是数据结构中有广泛的应用 . 关于加权图的应用 , 常常需要我们求解一棵无向生成树 , 使其边的总权值最小 . 这样的一棵生成树称作最小生成树 . 许多应用问题都是一个求 无向 连通图的最小生成树问题 . 例如 : 要在 n 个城市之间铺设光缆 , 主要目标是要使这 n 个城市的任意两个之间都可以通信 , 但铺设光缆的费用很高

2、,且各个城市之间铺设光缆的费用不同 ; 另一个目标是要使铺设光缆的总费用最低 . 这就需要找到带权的最小生成树 . MST 性质 : 最小生成树性质 : 设 ( , )G V E 是一个连通网络 , U 是顶点集 V 的一个真子集 . 若 ( , )nuv 是 G 中一条 “一个端点在 U 中 (例如 : uU ), 另一个端点不在 U 中 ”的边(例如 : v V U ), 且 (, )uv 具有最小权值 , 则一定存在 G 的一棵最小生成树包括此边1(, )uv . 求 MST 的一般算法可描述为 : 针对图 G , 从空树 T 开始 , 往集合 T 中逐条选择并加入 1n 条安全边 (,

3、 )uv , 最终 生成一棵含 1n 条边的 MST. 当一条边 (, )uv 加入 T 时 , 必须保证 ( , )T u v 仍是 MST 的子集 , 我们将这样的边称为 T 的安全边 . 其中主要有两种算法 : Prim 算法和 Kruskal 算法 . Prim 算法 : 该算法由 Prim 提出 , 但事实上 Jarnik 于 1930 年更早提出 . 用于求无向图的最小生成树 . 设图 ,G V E . 步骤 1: 取一个顶点 1v , 则 1Vv , E . 步骤 2: 选取与 jvV 邻接的 V 的最近邻元 iv , 并且边 ,ijvv不与 E 中元素形成回路 . 则添加 iv

4、 到 V 中 , 添加 ,ijvv到 E 中 . 步骤 3: 重复步骤 2 直到 V 包含图 G 所有顶点 , 则 此时 E 包含图 G 的最小生成树的边 . Prim 算法实现： （ 1）集合 : 设置一个数组 0,1, , 1se t i n, 初始值为 0 , 代表对应顶点不在集合中（注意 : 顶点号与下标号差 1） . （ 2） 图用邻接矩阵或邻接表表示 , 路径不通用无穷大表示 , 在计算机中可用一个大整数代替 . Kruskal 算法 : 每次选择 1n 条边 , 所使用的贪婪准则是 : 从剩下的边中选择一条不会产生环路的具有最小 权 的边加入已选择的边的集合中 . 注意到所选取的

5、边若产生环 路 , 则不可能形成一棵生成树 . Kruskal 算法 分 e 步 , 其中 e 是网络中边的数目 . 按耗费递增的顺序来考虑这 e 条边 , 每次 只 考虑一条边 . 当考虑某条边时 , 如果 将其加入到已选边的集合中会出现环路 , 则将其抛弃 , 否则 , 把 它选入 9 . 假设 ,WN V E 是一个含有 n 个顶点的连通网 , 则 根据 Kruskal 算法 构造最小生成树的过程为 : 先构造一个只含 n 个顶点 , 而边集为空的子图 , 若将该子图中 的 各个顶点看成是各棵树上的根结点 , 则它是一个含有 n 棵树的一个森林 . 然后 , 从网的边集 E 中选取一条权

6、值最小的边 , 若该边的两个顶点分 别 属 于 不同的树 , 则将其加入子图 , 也就是说 , 将这两个顶点分别所在的两棵树合成一棵树 ; 反之 , 若该条边的两个顶点已 经 在同一棵树上 , 则不可取 , 而应该取下一条权值最小的边再 尝试 . 依次类推 , 直至森林中只有一棵树 , 也即子图中含有 1n 条边为止 . 对于一个随机加权无向图 , 寻找其最小生成树的问题有许多重要的应用 , 而且解决此问题的算法至少从 1920年就已经出现 . 然而 , 研究人员仍在寻求更好的方法 . 因为这个问题并没有得到完全的理解 3 . 经典的 MST算法其实现的效率大相径庭 , 这些算法（例如 Bor

7、uvka、Prim算法等）在做运算时大都要求一次将数据读入内存中以做比较 , 如果处理的是大型图 , 内存没办法在一次就把所有的数据读入时 , 这些算法将受到一定局限性（虽然也有一些片外排序的技术 , 但其实现也不容易） . 针对这个问题 , 罗竣友 , 赵军辉 4 等提出的一种新的算法以实现在无向连通图中寻找最小生成树 , 基于分治法 5 的思想 , 将主要的排序分为两部分 , 在每部分中的子运算只需求读入内存很少的数据以做比较 . 最小生成树不仅在计算科学中有很大应用 , 而且 在 信息 , 遗传问题 , 生物地理甚至在配电网架优化规划 等方面都有着及其积极的作用 . 陶午沙 , 沈振康

8、, 李吉成 6 提出一种融合多元模糊空间关系信息的支撑树搜索算法 ,即S2Prim(spatial Prim)算 法 , 用以识别低分辨率环境下 (红外、多光谱遥感、 SAR、恒星导航等图像中 )具有规则空间分布关系的目标斑点集合 . 徐磊 , 张兢 7 引入了节点的度的定义 , 据此提出了广义最小生成树的概念 . 采用遗传算法来求解最小生成树 , 井针对普通遗传算法求解该问题的不足 , 提出了自调整的变异算子和限制父代个体数目的混合选择策略 , 通过一个有线电视网络的建摸与仿真 , 表明了广义最小生成树模型的适用性 . 分别采用普通遗传算法和改进后的遗传算法进行求解 , 井将结果进行比较 ,

9、 证明了 改进后的遗传算法的有效性 . 刘健 , 杨文宇 , 余健明 , 宋蒙 8 提出了一种用于配电网络规划的改进最小生成树算法：将配电网的电源点和负荷点当作顶点 , 将各个顶点间可能架设线路的走廊当作边 , 将线路的建设费用和运行费用 (主要为线损 )之和作为各条边的权 , 在采用基本最小生成树算法获得初步规划方案的基础上 , 采取动态调整各条边的权值并反复迭代的方法 , 获得总费用最小的优化规划结果 , 并采用随机初始权值的处理方法以提高获得全局最优解的机会 . 目前最小生成树仍以其广泛的 用途和极具逻辑的运算被广大学者和研究员等研究着 , 最近的理论成果亦很丰富 . 像 对求解加权连通

10、无向图最小生成树的 Kruskal算法进行了探讨 ,并用 VB实现 , 同时以读取文件的方法输入图 , 弥补了利用面向过程的程序设计语言在求解最小生成树时输入数据的复杂性 . 通过可视化的形式显示无向图和最小生成树 , 使结果直观且容易理解 . 还有一种基于最小生成树的多目标进化算法 MST_MOEA9 , MST_MOEA在考虑了个体间支配关系的基础上 , 利用个体与非支配集的距离和不 同等级个体的树聚集密度来对适应度赋值 ; 在外部种群中非支配个体数目超过规定规模时 , 用最小生成树的度数和树聚集密度对其进行修剪 ; 将 MST_MOEA应用于不同维数下的 9个测试函数 , 并和 NSGA

11、2II, SPEA2进行比较实验 ,结果表明 MST_MOEA具有良好的搜索性能 . 甚至在矿井通风系统网络中 , 无论是自然分风计算 , 还是调节计算以及调节设施的合理布局都要用到最小生成树 . 因此 , 最小生成树 是一种很有现实意义的算法 , 熟练的运用 最小生成树的几种重要算法可以解决各类 现实 问题 . 算法的诸多优势也自然 越发受 到数学、计算机等不同领域内学者的重视 . 参考文献 1 马叔良 . 离散数学 M. 北京 : 电子工业 出版社 , 2009. 319320. 2 王元元 , 张桂芸 .计算机科学中的离散结构 M. 北京 : 机械 工业出版社 , 2004, 15(4)

12、: 23 25. 3 Seth Pettie, Vijaya Ramachandran, An Optimal Minimum Spanning Tree Algorithm J, Journal of the ACM, 2002, 49(1): 1634. 4 Anany Levitin, Introduction to The Design and Analysis of AlgorithmsM, 北京 : 清华大学出版社 , 2004 . 5 罗竣友 , 赵军辉 . 一种新的最小生成树算法 J. 澳门科技大学 , 2009, 35(3): 17931797. 6 陶午沙 , 沈振康 , 李吉成 . 一种基于模糊信息融合的 Prim 算法及应用 J. 国防科技大学 , 2005, 3, (26): 8081. 5 徐磊 , 章兢 . 广义 最小生成树的遗传算法求解及应用 J. 系统工程与电子技术 , 2004,26(3):390392. 8 刘健 , 杨文宇 , 余健明 , 宋蒙 . 一种基于改进最小生成树算法的配电网架优化规划 J. 西安科技大学银河西科自动化研究所 ,2004,8,9. 9 李密青 , 郑金华 , 罗彪 . 一种基于最小生成树的多目标进化算法 J. 计算机研究与发展 , 2009, 46(5): 803813.