1、 本科毕业论文 （ 20 届） 最小生成树算法及其应用 所在学院 专业班级 信息与计算科学 学生姓名 学号 指导教师 职称 完成日期 年 月 I 摘 要 最小生成树是图论中的一个既经典又重要的问题 . 它体现在图这种数据结构上的应用涉及到我们的日常 , 工程 , 学术以 及科研等方方面面 . 最小生成树广泛的应用价值主要取决于其通俗简单的理论算法和严密成熟的数学基础 . 本文首先介绍最小生成树的相关理论 ; 其次给出几种最小生成树的经典算法 , 在此基础上对这些算法的优缺点进行分析比较 , 得到一些相关结论 ; 最后介绍最小生成树经典算法以及最小生成树在各领域中的几种代表算法的应用 . 关键词
2、 : 最小生成树 ; Prim 算法 ; Kruskal 算法 ; 应用 II Abstract Minimum spanning tree is both a classic and important issues in graph theory. The applications of minimum spanning tree reflecting on the data structure related to serial aspects of our daily life, engineering, academic and scientific research. Its wi
3、dely applications depend on simple theory and strict mature mathematical basis. Firstly, this thesis introduces some basic theories about minimum spanning tree; Secondly, it gets some kinds of classic algorithms, on this basis, it analyzes and compares the advantages and disadvantages of these algor
4、ithms, then achieves some conclusion; Lastly, it introduce applications of both classic algorithms and those representative algorithms in many areas. Keywords: Minimum spanning tree; Prim algorithm; Kruskal algorithm; Applications III 目录 摘 要 .I Abstract . II 1 前言 . 1 2 最小生成树的定义及性质 . 3 2.1 最小生成树定义 .
5、3 2.2 最小生成树的性质 . 4 3 最小生成树的两种经典算法 . 6 3.1 Prim 算法 . 6 3.2 Kruskal 算法 . 6 3.3 算法分析与比较 . 7 4 经典算法及改进算法的应用 . 8 4.1 Prim 算法应用 . 8 4.2 Kruskal 算法应用 . 8 4.3 其它算法与应用 . 12 5 小结 . 14 参考文献 . 15 致谢 . 17 1 1 前言 树是图论的重要内容 , 在计算机科学技术 , 特别是数据结构中有广泛的应用 . 关于赋权图的应用 , 常常需要我们求解一棵无向生成树 , 使其边的总权值最小 . 这样的一棵生成树称作最小生成树 (min
6、imum spanning tree, MST). 最小生成树算法也是重要的计算方法 , 是现代科学中比较热门的研究方向 . 许多应用问题都是一个求 无向 连通图的最小生成树问题 . 例如 : 要在 n 个城市之间铺设光缆 , 主要目 标是要使这 n 个城市的任意两个之间都可以通信 , 但铺设光缆的费用很高 , 而 且各个城市之间铺设光缆的费用不同 ; 另一个目标是要使铺设光缆的总费用最低 . 这就需要找到带权的最小生成树 . 许多研究工作表明 , 最小生成树结构是通信网络设计的最优拓扑结构 . 然而 , 实际的网络优化问题通常需要满足附加的约束 . 因此形成了带约束的最小生成树问题 , 例如
7、 : （ 1） 概率最小生成树问题 ; （ 2） 叶子约束最小生成树问题 ; （ 3） 随机最小生成树问题 ; （ 4） 容量限制的最小生 成树问题等 . 最小生成树算法从 1920年就已经出现 . 然而 , 研究人员仍在寻求更好的方法 . 因为这个问题并没有得到完全的理解 1 . 经典的 MST算法其实现的效率大相径庭 , 这些算法（例如Boruvka, Prim算法等）在做运算时大都要求一次将数据读入内存中以做比较 , 如果处理的是大型图 , 内存无法一次就把所有的数据读入 , 这些算法将受到一定局限性（虽然也有一些片外排序的技术 , 但其实现也不容易） . 针对这个问题 , 罗竣友 ,
8、尤众 , 赵军辉 2 等提出了一种新的算法以实现在无向连通图中寻找最小生成树 , 该算法基于分治法 3 的思想 , 将主要的排序分为两部分 , 在每部分中的子运算只要求读入内存很少的数据以做比较 . 陶午沙 , 沈振康 , 李吉成 4 提出一种融合多元模糊空间关系信息的支撑树搜索算法 , 即S2Prim(spatial Prim)算法 , 用以识别低分辨率环境下 (红外、多光谱遥感、 SAR、恒星导航等图像中 )具有 规则空间分布关系的目标斑点集合 . 徐磊 , 张兢 5 引入了节点的度的定义 , 据此提出了广义最小生成树的概念 . 采用遗传算法来求解最小生成树 , 井针对普通遗传算法求解该问
9、题的不足 , 提出了自调整的变异算子和限制父代个体数目的混合选择策略 , 通过一个有线电视网络的建摸与仿真 , 表明了广义最小2 生成树模型的适用性 . 分别采用普通遗传算法和改进后的遗传算法进行采解 , 井将结果进行比较 , 证明了改进后的遗传算法的有效性 . 刘健 , 杨文宇 , 余健明 , 宋蒙 6 提出了一种用于配电网络规划的改进最小生成树算法 :将配电网的电源点和负荷点当作顶点 , 将各个顶点间可能架设线路的走廊当作边 , 将线路的建设费用和运行费用 (主要为线损 )之和作为各条边的权 , 在采用基本最小生成树算法获得初步规划方案的基础上 , 采取动态调整各条边的权值并反复迭代的方法
10、 , 获得总费用最小的优化规划结果 , 并采用随机初始权值的处理方法以提高获得全局最优解的机会 . 当然国内外不断还有很多优秀的改进算法应用在各个领域中 , 这些算法正逐渐显现出其优越性 . 本文研究 的基本思路是 : 根据上文的介绍 , 对最小生成树的经典和常用算法进行分析与研究 , 以此 , 对算法的优缺点及适用的应用进行更深入的分析 . 具体的论文安排如下 : 第一章 , 主要介绍最小生成树的背景 , 应用以及全文的内容安排 . 第二章，主要简略地介绍最小生成树的基本理论 . 给出了最小生成树的定义和性质 . 第三章，主要就最小生成树的经典算法做一些讨论 . 首先 , 介绍两种算法的描述
11、和实现 ,包括 Prim 算法和 Kruskal 算法 . 其次 , 从理论上对这两种算法的复杂性和优缺点进行分析比较 , 并得出适用范围 . 第四章 ，主要介绍最小生成树各种算法的应用领域和其应用前景 , 其中重点举例解析了运用 Kruskal 算法解决实际问题的过程 . 第五章，对全文进行小结，并给出本文所得到的一些结论 . 3 2 最小生成树的定义及性质 本章将给出与下文讨论相关的最小生成树的基本理论 . 首先 , 我们将给出最小生成树的基本定义和表示形式 ; 然后 , 介绍最小生成树的性质及图论的基本理论 . 2.1 最小生成树定义 图论以图为研究对象 , 是数学的一个分支 . 图论中
12、的图是由若干个给定的点及连接两点的线所构成的图形 , 这种图形通常用来描述某些事 物之间的某种特定关系 , 用点来代表事物 , 用连接两点的线来表示相应两个事物间具有这种关系 . 定义 2.1 图 G 由两个部分组成 : （ 1）非空集合 V , 称为图 G 的顶点集 . （ 2）多重集合 E , 称为图 G 的边集 . 定义 2.2 图 G 的顶点 1v 到顶点 lv 的拟路径是指如下的序列 : 1 1 2 2 3 1 1, , , , , , , ,l l lv e v e v v e v. 其中 ( 1,2, , )iv i l 是 G 的顶点 , ( 1, 2, , 1)je j l是
13、 G 的边 . 当 ( 1, 2, , 1)je j l全不相同时 , 该拟路径称为路径 , 又当 ( 1,2, , )iv i l 各不相同时（除 1v 和 lv 外） , 则称此路径为通路 . 1 lvv 的路径称为闭路径 , 1 lvv 的通路称为回路 . 定义 2.3 在一个无向图 G 中 , 若从顶点 v 到顶点 v 有路径相连（当然从 v 到 v 也一定会有路径） , 则称 v 和 v 是连通的 . 定义 2.4 如果图中任意的两点都是连通的 , 那么显然这个图就是连通图 . 下面我们逐步引出最小生成树的概念 : 定理 2.1 命题 “ ,nm 图 T 为树 (其中 n 是顶点数
14、, m 是边数 )“ 与下面 5 个命题中的每一个命题都等价 : （ 1） T 无回路且 1mn. （ 2） T 连通且 1mn. （ 3） T 无回路 , 但任意地添加边时 , T 中产生惟一一条回路 . （ 4） T 连通 , 但删除任一边时就不再连通 . （ 5）任意两个不同顶点间有且仅有一条通路 . 4 定义 2.5 当图的边都有向时 , 称该图为有向图 ; 当图的边都无向时 , 称该图为无向图 . 定义 2.6 边 ,e uv 时 , 称 u 和 v 是边 e 的端点 , 当 uv 时 , ,uv 称为环 . 定义 2.7 连通无回路的无向图称为无向树 . 有了这些图论和树的基础知识
15、 , 我们就能很 容易地理解最小生成树的相关定义了 . 定义 2.8 设图 1 1 1,G V E ， 2 2 2,G V E , 如果 12VV ， 12EE , 则称 1G 为 2G的子图 , 当 12VV 时 , 称 1G 为 2G 的生成子图 . 定义 2.9 如果图 T 是无向图 G 的生成子图且 T 是树 , 则 T 是 G 的生成树 . 定义 2.10 当给图 G 赋予映 射 :f V W , 或 :g E W , W 为任意集合 , 则此时称G 为赋权图 . fv称为顶点 v 的权 , ge称为边 e 的权 . 定 义 2.11 设 G 为连通的边赋权图 , T 为 G 的生成
16、树 , 则 T 的各边权之和 eTW T W e 称为生成树 T 的权 , 权最小的生成树称为最小生成树 . 2.2 最小生成树的性质 本小节将通过介绍最小生成树的具体性 质来更好地揭示最小生成树的本质 . 定理 2.27 T 是树的充要条件是 T 中无环 , 且任何不同的两顶点之间有且仅有一条路径 . 证明 必要性 : 反证法 . 已知 任意 , ( )x y V T （ xy ） , 由于 T 是连通图 , 则 x 与 y 之间一定有路径 . 设 1P 和 2P 是 T 中两条不同的 x 到 y 的路径 , 则 12PP为闭路径 , 且存在边1eP , 但 2eP . 显然子图 12P P
17、 e 是连通图 . 设 ,e uv , 则子图 12P P e 中存在u 到 v 的路径 P , 于是 Pe 是圈 . 这与已知矛盾 . 所以树 T 的任何不同两顶点间有且仅有一条路 . 充分性 : 假设 T 中含圈 C . 若 ( ) 1Vc , 则 T 中有环 ; 若 ( ) 2Vc , 则 T 中有平行边 ;若 ( ) 3Vc , , ( )x y V c , 有两条不同的 x 到 y 的路径 . 这些都与已知是矛盾的 , 因此 T是无圈连通图 , 即 T 为树 . 5 定义 2.12 设 ( , )G V E 是一个 连通网络 , U 是顶点集 V 的一个真子集 . 如果 ( , )n
18、uv是 G 中一条 “一个端点在 U 中 (例如 : uU ), 而 另一个端点不在 U 中 (例如 : v V U )”的边 , 且 (, )uv 具有最小权值 , 则一定存在 G 的一棵最小生成树包括此边 8( , )uv . 求 最小生成树 的一般算法可描述为 : 针对图 G , 从空树 T 开始 , 往集合 T 中逐条选择并加入 1n 条 赋权 边 (, )uv , 最终生成一棵含 1n 条边的 最小生成树 . 6 3 最小生成树的两种经典算法 最小生成树 主要有两种算法 : Prim 算法和 Kruskal 算法 . 本章将重点探讨最小生成树的这两种非常经典且极具代表性的算法 . 这
19、两种算法的基本思想是 : 当一条边 (, )uv 加入 T 时 , 必 须保证 ( , )T u v 仍是 MST 的子集 . 3.1 Prim 算法 Prim 算法 描述 : 该算法由 Prim 于 1957 年 提出 , 但事实上 Jarnik 于 1930 年更早提出 . 用于求无向图的 最小生成树 . 设图 ,G V E . 步骤 1: 取一个顶点 1v , 则 1Vv , E . 步骤 2: 选 取与 jvV 邻接的 V 的最近邻元 iv , 并且边 ,ijvv不与 E 中元素形成回路 . 则添加 iv 到 V 中 , 添加 ,ijvv到 E 中 . 步骤 3: 重复步骤 2 直到
20、V 包含图 G 所有顶点 , 则此时 E 包含图 G 的最小生成树的边 . Prim 算法实现： （ 1） 集合 : 设置一个数组 0,1, , 1se t i n, 初始值为 0, 代表对应顶点不在集合中（注意 : 顶点号与下标号 差 1） . （ 2） 图用邻接矩阵或邻接表表示 , 如果两个顶点之间没有 路径 则 用无穷大表示 , 在计算机中可用一个大整数代替 . 3.2 Kruskal 算法 Kruskal 算法 : 每次选择 1n 条边 , 所使用的贪婪准则是 : 从剩下的边中选择一条不会产生环路的具有最小 权 的边加入已选择的边的集合中 . 注意到所选取的边若产生环 路 , 则不可能形成一棵生成树 . Kruskal 算法 分 e 步 , 其中 e 是网络中边的数目 . 按耗费递增的顺序来考虑这 e 条边 , 每次 只 考虑一条边 . 当考虑某条边时 , 如果 将其加入到已选边的集合中会出现环路 , 则将其抛弃 , 否则 , 把 它选入 9 . 假设 ,WN V E 是一个含有 n 个顶点的连通网 , 则 根据 Kruskal 算法 构造最小生成树的过程为 : 先构造一个只含 n 个顶点 , 而边集为空的子图 , 若将该子图中 的 各个顶点看成是各棵树上的根结点 , 则它是一个含有 n 棵树的一个
