普里姆算法求最小生成树doc

《普里姆算法求最小生成树doc》由会员分享，可在线阅读，更多相关《普里姆算法求最小生成树doc（24页珍藏版）》请在金锄头文库上搜索。

1、沈阳航空航天大学 课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目：PrimPrim 算法求最小生成树算法求最小生成树 院（系）：计算机学院 专 业： 计算机科学与技术（物联网方向） 班 级： 学 号： 姓 名： 指导教师： 学术诚信声明 本人声明本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指 导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别 加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表 或撰写过的研究结果，也不包含其它教育机构使用过的材料。与我一 同工作的同学对本研究所做的任何贡献均己在报告中做了明确的

2、说明 并表示了谢意。报告资料及实验数据若有不实之处，本人愿意接受本 教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后 果。 本人签名: 日期： 2015 年 1 月 15 日 沈阳航空航天大学沈阳航空航天大学 课课程程设设计计任任务务书书 课程设计名称 数数据据结结构构课课程程设设计计专业 计算机科学与技术计算机科学与技术 （物联网方向）（物联网方向） 学生姓名班级学号 题目名称PrimPrim 算法生成最小生成树算法生成最小生成树 起止日期20152015年1 1月5 5日起至20152015年1 1月1616日止 课设内容和要求： 在 n 个城市之间建立网络，只需保证连通即可，

3、求最经济的架设方法，利用 Prim 算法输出 n 个城市之间网络图，输出 n 个节点的最小生成树。其中，n 个城 市表示 n 个节点，两个城市间如果有路则用边连接，生成一个 n 个节点的边权树， 要求键盘输入。 参考资料： 算法与数据结构，严蔚敏、 吴伟民，清华大学出版社，2006 C 语言程序设计，谭浩强，清华大学出版社，2010 教教研研室室审审核核意意见见： 教教研研室室主主任任签签字字： 指导教师（签名）指导教师（签名） 年月日 学学 生（签名）生（签名）20152015年1 1 月 15 日 目目 录录 学术诚信声明学术诚信声明 .- - 1 1 - - 一一 课程设计目的和要求课程

4、设计目的和要求 .- - 4 4 - - 1.1 课程设计目的 .- 4 - 1.2 课程设计的要求 .- 4 - 二二 实验原理分析实验原理分析 .- - 5 5 - - 2.1 最小生成树的定义 .- 5 - 2.2 PRIM算法的基本思想.- 5 - 三三 概要分析和设计概要分析和设计 .- - 7 7 - - 3.1 概要分析 .- 7 - 3.2 概要设计 .- 8 - 四四 测试结果测试结果 .- - 1313 - - 4.1实验一.- 13 - 4.2实验二.- 13 - 4.3 实验三 .- 14 - 参考文献参考文献 .- - 1515 - - 附附 录（关键部分程序清单）录

5、（关键部分程序清单） .- - 1616 - - 一 课程设计目的和要求 1.11.1 课程设计目的课程设计目的 (一)根据算法设计需要，掌握连通网的数据表示方法； (二)掌握最小生成树的 Prim 算法； (三)学习独立撰写报告文档。 1.21.2 课程设计的要求课程设计的要求 在 n 个城市之间建立网络，只需保证连通即可，求最经济的架设方法，利用 Prim 算法输出 n 个城市之间网络图，输出 n 个节点的最小生成树。其中，n 个城 市表示 n 个节点，两个城市间如果有路则用边连接，生成一个 n 个节点的边权树， 要求键盘输入。 二 实验原理分析 2.12.1 最小生成树的定义最小生成树的

6、定义 一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中 的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用 kruskal（克鲁斯卡尔）算法或 Prim（普里姆）算法求出。 (1). 最小生成树的概述 在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边 （即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循 环图，使得 w(T) 最小，则此 T 为 G 的最小生成树。 最小生成树其实是最小权重生成树的简称。 (2). 最小生成树的分析 构造最小生成树可以用多种算法。其中多数算法利用了最小生

7、成树的 下面一种简称为MST 的性质：假设N=(V,E)是一个连通网， U 是顶点 集 V 的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中 uU，vV-U，则必存在一棵包含边(u.v)的最小生成树。 2.22.2 PrimPrim 算法的基本思想算法的基本思想 假设 G =（V，E）是一个具有 n 个顶点的连通网，T=(U,TE)是 G 的最小生成 树，其中 U 是 T 的顶点集，TE 是 T 的边集，U 和 TE 的初值均为空集。算法开始 时，首先从 V 中任取一个顶点（假定取 V0） ，将它并入 U 中，此时 U=V0，然后 只要 U 是 V 的真子集，就从那些其一个端点

8、已在 T 中，另一个端点仍在 T 外的所 有边中，找一条最短（即权值最小）边，假定为（i,j） ，其中 ViU,Vj(V-U), 并把该边（i,j）和顶点 j 分别并入 T 的边集 TE 和顶点集 U，如此进行下去，每 次往生成树里并入一个顶点和一条边，直到 n-1 次后就把所有 n 个顶点都并入到 生成树 T 的顶点集中，此时 U=V，TE 中含有 n-1 条边，T 就是最后得到的最小生 成树。可以看出，在普利姆算法中，是采用逐步增加 U 中的顶点，常称为“加点 法” 。为了实现这个算法在本设计中需要设置一个辅助数组 closedge ，以记录 从 U 到 V-U 具有最小代价的边。当辅助数

9、组中存在两个或两个以上的最小代价的 边时，此时最小生成树的形态就不唯一，此时可以在程序中采用递归的算法思想 求出每个最小生成树。 (1). 在 prim 算法中要解决两个问题 1)在无向网中，当从一个顶点到其他顶点时，若其边上的权值相等，则可能从 某一起点出发时，会得到不同的生成树，但最小生成树的权值必定相等，此 时我们应该如何把所有的最小生成树求解出来； 2)每次如何从生成树 T 中到 T 外的所有边中，找出一条权值最小的边。例如， 在第 k 次（1kn-1）前，生成树 T 中已有 k 个顶点和 k-1 条边，此时 T 中到 T 外的所有边数为 k(n-k)，当然它也包括两顶点间没有直接边相

10、连，其 权值被看作常量的边在内，从如此多的边中找出最短的边，其时间复杂度 0（k（n-k） ） ，是很费时间的，是否有好的方法能够降低查找最短边的时间复 杂度。 (2). 上述问题的解决方法 针对 1）中出现的问题，可以通过算法来实现，详情请看 Prim 算法的概述； 针对 2）中出现的问题，通过对 Prim 算法的分析，可以使查找最短边的时间 复杂度降低到 O(n-k)。具体方法是假定在进行第 k 次前已经保留着从 T 中到 T 外 的每一顶点（共 n-k 个顶点）的各一条最短边，进行第 k 次时，首先从这 n-k 条 最短边中，找出一条最最短的边，它就是从 T 中到 T 外的所有边中的最短

11、边，假 设为（i,j） ，此步需进行 n-k 次比较；然后把边（i,j）和顶点 j 分别并入 T 中 的边集 TE 和顶点集 U 中，此时 T 外只有 n-(k+1)个顶点，对于其中的每个顶点 t，若（j,t）边上的权值小于已保留的从原 T 中到顶点 t 的最短边的权值，则用 （j,t）修改之，使从 T 中到 T 外顶点 t 的最短边为（j,t） ，否则原有最短边保 持不变，这样，就把第 k 次后从 T 中到 T 外每一顶点 t 的各一条最短边都保留下 来了，为进行第 k+1 次运算做好了准备，此步需进行 n-k-1 次比较。所以，利用 此方法求第 k 次的最短边共需比较 2(n-k)-1 次

12、，即时间复杂度为 O(n-k)。 三 概要分析和设计 3.13.1 概要分析概要分析 通过对上述算法的分析，将从以下三方面来进行分析： (1). 输入数据的类型 在本次设计中，是对无向图进行操作，网中的顶点数，边数，顶点的编号及 每条边的权值都是通过键盘输入的，他们的数据类型均为整型，其中，权值的范 围为 032768（即“” ） ； (2). 输出数据的类型 当用户将无向图创建成功以后，就可以通过键盘任意输入一个起点值将其对 应的最小生成树的生成路径及其权值显示出来； (3). 测试数据 本次设计中是通过用 Prim 算法求最小生成树，分别用以下三组数据进行测 试： (一)假设在创建无向图时，只输入一个顶点，如图 1 所示，验证运行结果； 图 1.单一节点的无向图 (二)假设创建的无向图如图 2 所示，验证运行结果； A 图 2.网中存在权值相等的边 (三)假设创建的无向图如图 3 所示，验证结果； 图 3，网中的权值各不相等 3.23.2 概要设计概要设计 在本次设计中，网的定义为 G=(V,E),V 表示非空顶点集,E 表示边集,其存储 结构这里采用邻接矩阵的方式来存储。 1 数据类型的定义 在本设计中所涉 及到的数据类型定义如下： (1). 符