1、数 据 结 构 与 算 法 课 程 设 计 报 告 - 1 - 计算机科学与技术系 课程设计报告 20092010 学年 第 二 学期 课程课程 数据结构与算法 课 程 设 计 名 称课 程 设 计 名 称 最小生成树求解 学生姓名学生姓名 学号学号 专业专业班级班级 指导教师指导教师 2010 年 6 月 数 据 结 构 与 算 法 课 程 设 计 报 告 - 2 - 1 1 课程设计课程设计题目题目 对任意给定的网和起点， 用PRIM算法的基本思想求解出所有的最小生成树。 2 2 问题分析和任务定义问题分析和任务定义 本课程设计重在使用 prim 算法实现任意给定的网和起点的图的所有最小生
2、成树的求 解，实现本课程设计的关键即是能够掌握 prim 算法的思想，并能够灵活使用。 首先我们必须对 prim 算法有个清晰地认识，prim 算法是普利姆（Prime）于 1957 年提 出了一种构造最小生成树的算法，算法的主要思想如下：按照将顶点逐个连通的步骤，把顶 点加入到已经连通的顶点集合 U 中，最后使得 U 成为最小生成树。 PRIM 思路：1）初始化顶点集合 U 为空集。 2）任意选取一个顶点 v 加入 U。 3）选取一条权值最小的边（u,v） ，其中 uU，v（V-U） ，将该边假如到生成树， v 加入到 U 中。 4）重复步骤 3） ，直到所有顶点均加入到 U 中构成一颗最小
3、生成树。 为了实现这一算法需要附设一个辅助数组closedgev用来存储从U到V-U之间具有最小代价 的边。对于每个顶点 v（V-U） ，在 closedge，树组中都存在一个分量 closedgev，它有 两个域组成。其中一个是权值，即： closedgev.lowcost=MINcost（u,v）|uU，另外一个是顶点域 vexs，存储依附于该边在 U 中的顶点。 其次，针对本课程设计的题目要求，我们需要考虑到五个问题： 如何选择、设计一个合适的算法来建立图，用以实现接下来的操作。 如何正确的在本实验中使用 prim 算法。 对于本课程设计中的需要，求出对于给定任意给定的网和结点，得出所有
4、的所有的最小生 成树，关键在于需要求出所有的最小生成树，需要灵活使用 prim 算法实现。 对于一些细节也是需要考虑斟酌的，比如，当所输入的顶点不存在时，需要一个示 语句警示，并能够重新输入。 当算法设计完成后，还需对于整个运行程序的运行界面，提示语句以及如何完美、 清楚的输出各个最小生成树设计一番。 最后，在课程设计过程中，自己需要做好充足的准备工作，吃透课本中关于 prim 算法的 解释说明，同时把握好时间，掌握整个课程设计的进度，做好整体规划，保证本次课程设计 可以及时的、成功的设计出来。 3 3 数据结构的选择和概要设计数据结构的选择和概要设计 对于本次设计，在 prim 算法中使用的图均为无向图，对于各顶点之间的权值以及连通 关系是采用邻接矩阵来实现的。同时在 prim 算法中采用了辅助数组 closedgev，主 要用来存储到顶点的最小边权值。 建立图的数据结构类型如下： typedef struct int vexsMAX; /顶点信息集合 int arcsMAXMAX
