I 合肥学院 计算机科学与技术系 课 程 设 计 报 告 2014-2015 学年第二学期 课程 数据结构 课程设计名称 Kruskal 算法求最小生成树 学生姓名 姚国栋 学号 ********** 专业班级 12 软件工程 指导教师 何立新 2014 年 9 月 2 题目：设计程序完成如下功能：对给定过的网和起点，用kruskal 算法的基本思想求解其所有的最小生成树 1 、问题分析和任务定义 根据课设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分析： 要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。 Kruskal 算法。该算法设置了集合A，该集合一直是某最小生成树的子集。在每步决定是否把边（u,v）添加到集合A 中，其添加条件是A∪{（u,v）}仍然是最小生成树的子集。我们称这样的边为A 的安全边，因为可以安全地把它添加到A 中而不会破坏上述条件。 2 数据结构的选择和概要设计 存储结构 定义一个结构体数组，其空间足够大，可将输入的字符串存于数组中。 struct edges {int bv; int tv; int w; }; 概要设计。 算法思想 ： 3 算法会先按照权重的非递减顺序对图中的边进行排序。然后从一个空子图开始，扫描这个有序表，试图把列表中的下一条边加到当前的子图中。当然，这种添加不应导致一个回路，如果产生回路，就把这条边跳过。当图的所有顶点都包含在所构造的树中以后，算法停止。 算法的基本思路是： K r u s k a l 算法每次选择 n- 1 条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l 算法分 e 步，其中 e 是网络中边的数目。按耗费递增的顺序来考虑这 e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。 假设每个点都有一对标号（dj,pj）,其中 d 是从起源点到点 j 的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；pj 则是从 s 到 j 的最短路径中 j 点的前一点。求解从起源点 s 到点 j 的最短路径算法的基本过程如下： 1） 初始化。起源点设置为：①ds=0,ps 为空；②所有其它点：di=∞,pi=？；③标记...
