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