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