1、数据结构课程设计报告 1 数据结构课程设计报告数据结构课程设计报告 院系：计算机学院院系：计算机学院 班级：软件班级：软件 121121 班班 姓名：姓名： 学号：学号： 题目：最小生成树题目：最小生成树 指导老师：指导老师： 数据结构课程设计报告 2 一、引言一、引言.3 二、设计题目二、设计题目 3 1.问题描述 . 3 2.系统要求 . 3 3.测试数据 . 4 4.实现提示 . 4 5.参考文献 . 4 6.运行环境 . 5 三、需求分析三、需求分析 5 1.如何选择存储结构去建立一个带权网络。. 5 2.如何在所选存储结构下输出这个带权网络。 5 3.如何实现 PRIM 算法和 Kr
2、uskal算法的功能。 . 5 4.如何从每个顶点开始找到所有的最小生成树的顶点。 6 5.如何输出最小生成树的边及其权值。 6 四、概要设计四、概要设计 6 2.图的存储结构 7 3.流程图 . 7 五、详细设计五、详细设计 8 1.主函数模块 8 2.对路径权值进行排序. 9 六、调试与分析六、调试与分析 13 七、测试结果七、测试结果 . 16 八、设计心得体会八、设计心得体会 16 附录（源代码）附录（源代码） 17 数据结构课程设计报告 3 摘要摘要 最小生成树是数据结构中图的一种重要应用，在图中对于 n 个顶点的连通 网可以建立许多不同的生成树，最小生成树就是在所有生成树中总的代价
3、 最小的生成树。 本课程设计是以邻接矩阵作为图的存储结构,分别采用 Prim 和 Kruskal 算法求最小生成树。Kruskal 算法和 Prim 算法是求最小生成树 的常用算法它们分别适用于稠密图和稀疏图。 最小生成树的应用非常的广， 如矿井通风设计和改造最优化方面以及如何搭建最短的网络线缆, 构建造 价最低的通讯网络 。 一、一、引言引言 本课程设计我们要解决的问题是图最小生成树问题。要用到图的先相 关数据结构和求最小生成树的两种数据结构算法普里姆算法和克鲁斯卡尔 算法，以及储存图的边和点的邻接矩阵。 本课程设计要解决的问题构造连通网的最小生成树 ,我们首先要做的 是创建一个邻接矩阵，用
4、以来存储图，然后我们要想好怎样利用普里姆算 法和克鲁斯卡尔算法来构造最小生成树。把这两种算法写入主函数，调试 好程序。最后写好报告。 二、二、设计题目设计题目 1.问题描述问题描述 若要在 n 个城市之间建设通信网络，只需要假设 n-1 条线路即可。如何以 最低的经济代价建设这个通信网，是一个网的最小生成树问题。 2.系统要求系统要求 利用克鲁斯卡尔算法求网的最小生成树。 利用普里姆算法求网的最小生成树。 要求输出各条边及它们的权值。 数据结构课程设计报告 4 3.测试数据测试数据 4.实现提示实现提示 通信线路一旦建成，必然是双向的。因此，构造最小生成树的网一定是无 向图。设图的顶点数不超过
5、 30 个，并为简单起见，网中边的权值设成小于 100 的整数，100 则表示没有路径。 5.参考文献参考文献 1 严蔚敏. 数据结构（C 语言版）M. 北京：清华大学出版社,1997. 2 谭浩强. C 程序设计（第三版）M. 北京：清华大学出版社，2005.1. 3 二霍红卫算法设计与分析西安西安电子科技大学出版社， 2005.113-127. 4 陈杰.计算机专业课程设计中的需求分析J.集美大学学报， 2009， 10(2)： 8992. 5 高一凡. 数据结构算法实现及解析M . 西安:西安电子科技大学出版 数据结构课程设计报告 5 社, 2002 6.运行环境运行环境 VC+6.0
6、三、三、需求分析需求分析 1.如何选择存储结构去建立一个带权网络。如何选择存储结构去建立一个带权网络。 此问题的关键在于如何实现 PRIM 算法和 Kruskal 算法，实现的过程中如 何得到构成最小生成树的所有顶点，此外输出也是一个关键问题所在，在 此过程中经过了多次调试。 2.如何在所选存储结构下输出这个带权网络。如何在所选存储结构下输出这个带权网络。 将图中的所有顶点存储到一个一维数组中，通过一个二维数组用邻接矩阵 连实现对各边权值的存储 3.如何实现如何实现 PRIM算法算法和和 Kruskal 算法算法的功能。的功能。 首先我们对 prim 算法的问题进行大致的概要分析： 假设 N=（V，E）是连通网，TE是 N 上最小生成树中边的集合。算法从 U=u0（u0V） ，TE=开始，重复执行下述操作：在所有 uU，vV-U 的边（u，v）E 中找一条代价最小的边（u0,v0）并入集合 TE，同时 v0 并入 U，直至 U=V 为止。此时 TE 中必有 n-1 条边，则 T=(V ,T
