普里姆算法求最小生成树.docVIP

沈阳航空航天大学 课 程 设 计 报 告 课程设计名称：数据结构课程设计 课程设计题目：Prim算法求最小生成树 院（系）：计算机学院 专 业： 计算机科学与技术（物联网方向） 班 级： 学 号： 姓 名： 指导教师： 学术诚信声明 本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。 本人签名: 日期： 2015 年 1 月 15 日 沈阳航空航天大学 课程设计任务书 课程设计名称 数据结构课程设计 专业 计算机科学与技术（物联网方向） 学生姓名 班级 学号 题目名称 Prim算法生成最小生成树 起止日期 2015 年 1 月 5 日起至 2015 年 1 月 16 日止 课设内容和要求： 在n个城市之间建立网络，只需保证连通即可，求最经济的架设方法，利用Prim算法输出n个城市之间网络图，输出n个节点的最小生成树。其中，n个城市表示n个节点，两个城市间如果有路则用边连接，生成一个n个节点的边权树，要求键盘输入。 参考资料： 算法与数据结构，严蔚敏、?吴伟民 教研室审核意见： 教研室主任签字： 指导教师（签名） 年 月 日 学 生（签名） 2015 年 1 月15 日 目 录 学术诚信声明 - 1 - 一 课程设计目的和要求 - 4 - 1.1 课程设计目的 - 4 - 1.2 课程设计的要求 - 4 - 二 实验原理分析 - 5 - 2.1 最小生成树的定义 - 5 - 2.2 Prim算法的基本思想 - 5 - 三 概要分析和设计 - 7 - 3.1 概要分析 - 7 - 3.2 概要设计 - 8 - 四 测试结果 - 13 - 4.1 实验一 - 13 - 4.2 实验二 - 13 - 4.3 实验三 - 14 - 参考文献 - 15 - 附 录（关键部分程序清单） - 16 -  一 课程设计目的和要求 1.1 课程设计目的 根据算法设计需要，掌握连通网的数据表示方法； 掌握最小生成树的Prim算法； 学习独立撰写报告文档。 1.2 课程设计的要求 在n个城市之间建立网络，只需保证连通即可，求最经济的架设方法，利用Prim算法输出n个城市之间网络图，输出n个节点的最小生成树。其中，n个城市表示n个节点，两个城市间如果有路则用边连接，生成一个n个节点的边权树，要求键盘输入。 二 实验原理分析 2.1 最小生成树的定义 一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或rim（普里姆）算法求出。 在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得 w(T) 最小，则此 T 为 G 的最小生成树。 最小生成树其实是最小权重生成树的简称。 2.2 Prim算法的基本思想 假设G =（V，E）是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开始时，首先从V中任取一个顶点（假定取V0），将它并入U中，此时U={V0}，然后只要U是V的真子集，就从那些其一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短（即权值最小）边，假定为（i,j），其中Vi∈U,Vj∈(V-U),并把该边（i,j）和顶点j分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后就把所有n个顶点都并入到生成树T的顶点集中，此时U=V，TE中含有n-1条边，T就是最后得到的最小生成树。可以看出，在普利姆算法中，是采用逐步增加U中的顶点，常称为“加点法”。为了实现这个算法在本设计中需要设置一个辅助数组closedge[ ]，以记录从U到V-U具有最小代价的边。当辅助数组中存在两个或两个以上的最小代价的边时，此时最小生成树的形态就不唯一，此时可以在程序中采用递归的算法思想求出每个最小生成树。 在prim算法中要解决两个问