普里姆算法求最小生成树课程设计报告

《普里姆算法求最小生成树课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、课程设计成果学院:计算机工程学院班级:计算机科学与技术学生姓名:学号:设计地点（单位）：设计题目:普里姆算法求最小生成树完成日期：2016年1月6日指导教师评语:_______________________________________________________________________________________________________________________________________________________________________________________________________

2、___________________________________________________________________成绩(五级记分制):_____________________教师签名:_____________________________目录1需求分析11.1系统目标11.2主体功能11.2开发环境12概要设计22.1功能模块划分22.2系统流程图32.2.1CreateMGraph()函数程序框图32.2.2普利姆函数程序框图42.2.3createALgraph()函数程序框图52.2.4邻接矩阵Output()输出函数程序

3、框图53详细设计63.1数据结构63.2模块设计83.2.1创建有向网图邻接矩阵存储83.2.2创建无向网图邻接矩阵存储93.2.3创建有向网图邻接表存储103.2.4创建无向网图邻接表存储113.2.5prim算法求最小生成树123.2.6输出邻接矩阵存储函数133.2.7输出邻接表存储函数143.2.8邻接表转换成邻接矩阵函数144测试154.1调试准备154.2调试结果165总结21参考文献22附录全部代码231需求分析针对现实生活中，许多地方需要考虑到如：邮递员送信，在n个城市之间建立通信网络等最短路径的问题，本应用程序正是基于这一现实问题，在v

4、c++的平台下，采用普里姆算法对此作出解决，本程序主要包含2大模块，分别为采用邻接矩阵（表）的存储方式建立带权的（有）无向网络图和利用普里姆算法对所建的网络图求最小代生成树。它的最终目的是以最经济、最实惠、最节约的方式解决生活中的最短路径问题，以求给人们提供更节约、更便利的生活。在图论中，常常将树定义为一个无回路连通图。对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。1.1系统目标根据课程设计题目的

5、相关要求，应该完成以下目标：1.能够先生成一个网图，该网图既能是无向网图，有能是有向网图；2.要求分别采用邻接矩阵和链接表存储来完成；3.最后打印输出最小生成树。1.2主体功能1.该程序会有菜单提示，可以根据需求进行选项：2.能够生成网图并确定其存储形式，且该网图可能为有向图也可能为无向图，并采用邻接表和邻接矩阵（起点、终点和权值）两种存储结构。3.可以建立带权图，并能够用Prim算法求该网图的最小生成树。1.2开发环境操作系统：Windows编译集成环境（IDE）：VC++6.0Visual33C++6.0（简称VC++6.0）是强大的C/C++软件开

6、发工具，使用非常广泛，已经成为程序员首选的开发工具。利用它不仅可以开发控制台应用程序，还可以开发WindowsSDK、MFC等应用程序。因为本课题主要利用C语言描述普利姆算法生成最小生成树，所以可以使用VisualC++6.0开发控制台程序。用VisualC++6.0编写C语言程序需要如下两个步骤，一是创建一个新的ViusalC++6.0控制台项目；二是在该项目中创建C程序文件，并编辑C语言程序。2概要设计2.1功能模块划分该程序可输入的数据可为100以内的整数；可建立带权图，并能用Prim算法求该图的最小生成树，带菜单提示，可以根据需求进行选择：如图2

7、.1所示。图2.1主程序模块图332.2系统流程图2.2.1CreateMGraph()函数程序框图建立图g的邻接矩阵：图的邻接矩阵可利用两个数组实现，一个是一维数组，用来存储图中的顶点信息；另一个是二维数组，用来存储图中顶点之间的关系，该二维数组称为邻接矩阵。如图2.2所示图2.2CreateMGraph()函数程序框图332.2.2普利姆函数程序框图普里姆算法中有多个循环，假设顶点的个数是n，则第一层循环的频度为n-1，第二层循环的频度为n，因此该算法的时间复杂度为O（n2），与网中的边数无关，因此普里姆算法适用于求边稠密的最小生成树。如图2.3图2

8、.3prim函数332.2.3createALgraph()函数程序框图定义整型