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

课程设计成果 学院: 计算机工程学院 班 级: 计算机科学与技术 学生姓名: 学 号: 设计地点 （单位）： 设计题目: 普里姆算法求最小生成树 完成日期： 2016年 1月6 日 指导教师评语:___________________________________ ________________________________________________________________ ______________________________________________________________________ _________________ ______________________________________________________________________ __________ 成绩(五级记分制):_____________________ 教师签名:_____________________________ 目录 1 需求分析1 1.1系统目标1 1.2 主体功能1 1.2 开发环境1 2 概要设计2 2.1功能模块划分2 2.2 系统流程图3 2.2.1CreateMGraph()函数程序框图3 2.2.2 普利姆函数程序框图4 2.2.3createALgraph()函数程序框图5 2.2.4 邻接矩阵Output()输出函数程序框图5 3 详细设计6 3.1数据结构6 3.2 模块设计8 3.2.1创建有向网图邻接矩阵存储8 3.2.2 创建无向网图邻接矩阵存储9 3.2.3创建有向网图邻接表存储10 3.2.4 创建无向网图邻接表存储11 3.2.5prim 算法求最小生成树12 3.2.6输出邻接矩阵存储函数13 3.2.7输出邻接表存储函数14 3.2.8邻接表转换成邻接矩阵函数14 4 测试15 4.1调试准备15 4.2 调试结果16 5 总结21 参考文献22 附录 全部代码23 1 需求分析 针对现实生活中，许多地方需要考虑到如：邮递员送信，在n个城市之间建 立通信网络等最短路径的问题，本应用程序正是基于这一现实问题，在vc++的平 台下，采用普里姆算法对此作出解决，本程序主要包含2大模块，分别为采用邻 接矩阵 （表）的存储方式建立带权的 （有）无向网络图和利用普里姆算法对所建 的网络图求最小代生成树。它的最终目的是以最经济、最实惠、最节约的方式解 决生活中的最短路径问题，以求给人们提供更节约、更便利的生活。在图论中， 常常将树定义为一个无回路连通图。对于一个带权的无向连通图，其每个生成树 所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的 最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优 问题就是一个最小生成树问题。 1.1系统目标 根据课程设计题目的相关要求，应该完成以下目标： 1.能够先生成一个网图，该网图既能是无向网图，有能是有向网图； 2.要求分别采用邻接矩阵和链接表存储来完成； 3.最后打印输出最小生成树。 1.2主体功能 1.该程序会有菜单提示，可以根据需求进行选项： 2.能够生成网图并确定其存储形式，且该网图可能为有向图也可能为无向图， 并采用邻接表和邻接矩阵 （起点、终点和权值）两种存储结构。 3.可以建立带权