数据结构课程设计-最小生成树.docx

数据结构课程设计报告设计题目: 最小生成树专业:x xxxxx 院系: 计算机学院姓名:x xxxxxxxx 学号: xxxxxx 时间: 2013 年 10月7日数据结构课程设计报告最小生成树-1-目录一、设计目的……………………………………………………………….-2- 二、算法思想分析………………………………………………………-2- 1. 算法思想………………………………………………………………..-3- 1 )普里姆( Prim )算法思想……………………………………………………….-3- 2) 克鲁斯卡尔( Kruskal )算法思想..........................................-3- 2. 系统采用的数据结构和算法………………………………-3- 三、算法的描述与实现……………………………………………….-4- 四、用户手册………………………………………………………………-7- 五、总结…………………………………………………………………….-10- 六、参考文献…………………………………………………………….-10- 七、附录(源代码) ………………………………………………...-10- 数据结构课程设计报告最小生成树-2- [ 摘要] 选择一颗生成树,使之总的消费最少,也就是要构造连通网的最小代价生成树( 简称为最小生成树) 的问题, 一颗生成树的代价就是树上各边的代价之和, 构造最小生成树可以有多种算法, 其中多数算法利用了 MST 的性质。关键词: 最小生成树连通图普里姆算法克鲁斯卡尔算法 MST 一、设计目的 1. 了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力; 2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; 3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 4. 训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法和作风。二、算法思想分析该设计的要求是在 n 个城市之间建设网络, 不仅要保证连通, 还要求是最经济的架设方法。根据克鲁斯卡尔和普里姆算法的不同之处, 该程序将城市个数大于十个时应用普里姆算法求最小生成树, 而城市个数小于十个时则应用克鲁斯卡尔进行计算。数据结构课程设计报告最小生成树-3- 1. 算法思想 1) 普里姆( Prim )算法思想 a) 选择从 0 节点开始,并选择 0 节点相关联的最小权值边,将与这条边相关联的另一顶点出列; b) 在出列的节点中相关联的所有边中选择一条不与另一个已出列的节点相关联的权值最小的边,并将该边相关联的节点出列; c) 重复 b) 直到所有的节点出列。 2) 克鲁斯卡尔( Kruskal )算法思想为了使生成树上总的权值之和最小, 应该使每一条边上的权值尽可能的小, 所以应从权值最小的边选起, 直至选出 n-1 条不能构成回路的权值最小的边位置。具体做法如下:首先构造一个含 n 个顶点的森林,然后按权值从小到大从连通图中选择不使森林中产生回路的边加入到森林中去, 直至该森林变成一棵树为止, 这棵树便是连通图的最小生成树。由于生成树上不允许有回路, 因此并非每一条居当前最小的边都可选。从生成树的构造过程可见,初始态为 n 个顶点分属 n 棵树, 互不连通, 每加入一条边, 就将两棵树合并为一棵树, 在同一棵树上的两个顶点之间自然相连通, 由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。 2. 系统采用的数据结构和算法 1) 数据结构 T ypedef int Vertextype; T ypedef int adimatrix[MaxVertexNum][MaxVertexNum]; T ypedef int Vertextype vexlist[MaxVertexNum]; 数据结构课程设计报告最小生成树-4- T ypedef int VexType; T ypedef int AdjType; T ypedef struct edgeElem edgeset[MaxVertexNum]; struct edgeElem {int fromvex;// 头顶点 int endvex;// 尾顶点 int weight;// 权}; T ypedef struct { int n; // 图的顶点个数 AdjType acrs[MAXVEX][MAXVEX];// 边信息}GraphMatrix; T ypedef struct {int start_vex,stop_vex;// 边的起点和终点 AdjType weight;// 边的权}Edge; Edge mst[5]; 2) 算法 Gre