《数据结构课程设计（论文）--最小生成树》毕业学术论文.doc

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