prim 和kruskal 算法分析课程设计

《prim 和kruskal 算法分析课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊长春大学课程设计纸一、设计目的1．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二、设计内容问题描述：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。基本要求：(1)建立n个城市的连通图；(2)设计其存储结构；(3)显示所

2、建立的图；用Prim和Kruskal两种方法实现求最经济的架设方法，即求解最小生成数，显示两种方法产生的树中包含的每条边。三．设计要求1.问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？2.逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。3.详细设计：定义相应的存储结构并写出各函数的伪

3、码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。4.程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。5.程序调试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序

4、清单和结果。共22页第22页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊长春大学课程设计纸6.结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。7.编写课程设计说明书。四、设计过程1、算法思想分析（1）Prim算法求最小生成树的主要思想：此算法是普利姆与1957年提出的一种构造最小生成树的算法，主要思想是：假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V),TE={}开始，重复执行下述操作：在所有u∈U,v∈V-U的边（u,v）∈E

5、中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，{E}）为N的最小生成树。对于最小生成树问题最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。（2）kruskal算法求最小生成树的主要思想及分析：Kruskall算法每次选择n-1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。Kruskal算法分e步，其中e是网络中边的数目。按耗费递增的

6、顺序来考虑这e条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。共22页第22页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊长春大学课程设计纸七个城市的连通图如下：共22页第22页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊长春大学课程设计纸流程图开始输入城市及边的个数输入起点终点权值邻接矩阵存储N最小权值Y输出邻接矩阵最小生成树结束共22页第22页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊长春大学课程设计纸

7、2、算法描述与实现Prim算法描述：通过邻接矩阵的建立，可以将任意两点的权值存入其中，便于进行各边的权值的比较修改，在普利姆算法中，为实现这个算法需附设一个辅助数组closedge，以记录从U到V-U具有最小代价的边，对每个顶点vi∈V-U,在辅助数组中存在一个相应分量closedge[i-1]，他包括两个域，其中lowcost存储该边上的权值。显然，closedge[i-1].lowcost=Min{cost(u,vi)

8、u∈U}从算法可以看出每加入一个顶点到U中，closedge数组都会发生相应的变化。程序模块之间的调用：在主函数中调用邻接矩阵的初始化函数，邻

9、接矩阵的生