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

沈阳航空航天大学课程设计报告课程设计名称:数据结构课程设计课程设计题目:Prim算法求最小生成树院(系):计算机学院专业:计算机科学与技术(物联网方向)班级:学号:姓名:指导教师:学术诚信声明本人声明:所呈交的报告(含电子版及数据文件)是我个人在导师指导下独立进行设计工作及取得的研究结果。尽我所知,除了文中特别加以标注或致谢中所罗列的内容以外,报告中不包含其他人己经发表或撰写过的研究结果,也不包含其它教育机构使用过的材料。与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。报告资料及实验数据若有不实之处,本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。本人签名:日期:2015年1月15日沈阳航空航天大学课程设计任务书课程设计名称数据结构课程设计专业计算机科学与技术(物联网方向)学生姓名班级学号题目名称Prim算法生成最小生成树起止日期2015年1月5日起至2015年1月16日止课设内容和要求:在n个城市之间建立网络,只需保证连通即可,求最经济的架设方法,利用Prim算法输出n个城市之间网络图,输出n个节点的最小生成树。其中,n个城市表示n个节点,两个城市间如果有路则用边连接,生成一个n个节点的边权树,要求键盘输入。参考资料:《算法与数据结构,严蔚敏、 吴伟民,清华大学出版社,2006》《C语言程序设计,谭浩强,清华大学出版社,2010》教研室审核意见:教研室主任签字:指导教师(签名)年月日学生(签名)2015年1月15日目录学术诚信声明 -1-一课程设计目的和要求 -4- -4- -4-二实验原理分析 -5- -5- -5-三概要分析和设计 -7- -7- -8-四测试结果 -13- 实验一 -13- 实验二 -13- -14-参考文献 -15-附录(关键部分程序清单) -16-,掌握连通网的数据表示方法;掌握最小生成树的Prim算法;学习独立撰写报告文档。,只需保证连通即可,求最经济的架设方法,利用Prim算法输出n个城市之间网络图,输出n个节点的最小生成树。其中,n个城市表示n个节点,两个城市间如果有路则用边连接,生成一个n个节点的边权树,要求键盘输入。,且包含原图中的所有n个结点,并且有保持图连通的最少的边。最小生成树可以用kruskal(克鲁斯卡尔)算法或Prim(普里姆)算法求出。最小生成树的概述在一给定的无向图G=(V,E)中,(u,v)代表连接顶点u与顶点v的边(即),而w(u,v)代表此边的权重,若存在T为E的子集(即)且为无循环图,使得w(T)最小,则此T为G的最小生成树。最小生成树其实是最小权重生成树的简称。最小生成树的分析构造最小生成树可以用多种算法。其中多数算法利用了最小生成树的下面一种简称为MST的性质:假设N=(V,{E})是一个连通网,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边,其中u∈U,v∈V-U,则必存在一棵包含边()的最小生成树。=(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算法中要解决两个问题在无向网中,当从一个顶点到其他顶点时,若其边上的权值相等,则可能从某一起点出发时,会得到不同的生成树,但最小生成树的权值必定相等,此时我们应该如何把所有的最小生成树求解出来;每次如何从生成树T中到T外的