《数据结构课程设计报告最小生成树Kruskal算法》由会员分享，可在线阅读，更多相关《数据结构课程设计报告最小生成树Kruskal算法（14页珍藏版）》请在金锄头文库上搜索。
1、 I 合肥学院计算机科学与技术系课程设计报告 2014-2015 学年第二学期课程 数据结构课程设计名称 Kruskal 算法求最小生成树学生姓名 姚国栋学号 1204091021专业班级 12 软件工程指导教师 何立新2014 年 9 月 2 题目：设计程序完成如下功能：对给定过的网和起点，用 kruskal 算法的基本思想求解其所有的最小生成树1、问题分析和任务定义根据课设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分析：要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便
2、以后的编程。Kruskal 算法。该算法设置了集合 A，该集合一直是某最小生成树的子集。在每步决定是否把边（u,v）添加到集合 A 中，其添加条件是 A （u,v）仍然是最小生成树的子集。我们称这样的边为 A 的安全边，因为可以安全地把它添加到 A 中而不会破坏上述条件。2 数据结构的选择和概要设计存储结构定义一个结构体数组，其空间足够大，可将输入的字符串存于数组中。struct edgesint bv;int tv;int w;概要设计。算法思想 ： 3 算法会先按照权重的非递减顺序对图中的边进行排序。然后从一个空子图开始，扫描这个有序表，试图把列表中的下一条边加到当前的子图中。当然，这种添
3、加不应导致一个回路，如果产生回路，就把这条边跳过。当图的所有顶点都包含在所构造的树中以后，算法停止。算法的基本思路是：K r u s k a l 算法每次选择 n- 1 条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l 算法分 e 步，其中 e 是网络中边的数目。按耗费递增的顺序来考虑这 e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。假设每个点都有一对标号（d j,pj）,其中 d 是从起源点到点 j 的最
4、短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路） ，其长度等于零） ；p j 则是从 s 到 j 的最短路径中 j 点的前一点。求解从起源点 s 到点 j 的最短路径算法的基本过程如下：1） 初始化。起源点设置为：d s=0,ps 为空；所有其它点：d i=,p i=？；标记起源点 s，记k=s，其他所有点设为未标记的。2） k 到其直接连接的未标记的点 j 的距离，并设置：dj=mindj, dk+lkj式中，l kj 是从点 k 到 j 的直接连接距离。3） 选取下一个点。从所有未标记的结点中，选取 dj 中最小的一个 i：di=mindj, 所有未标记的点 j点 i 就被选为最
5、短路径中的一点，并设为已标记的。4）找到点 i 的前一点。从已标记的点中找到直接连接到 i 的点 j*，作为前一点，设置： i=j*5)标记点 i。如果所有点已标记，则算法完全推出，否则，记 k=i，转到 2）再继续。而程序中求两点间最短路径算法。其主要步骤是： 调用 dijkstra 算法。 将 path 中的第“终点”元素向上回溯至起点，并显示出来。 4 3 详细设计和编码功能模块图开始输入顶点个数 n输入边数 e输入边集显示菜单，进行选择。求两点间最短距离求两点间最短距离Kruskal 算法结束图 3.1 功能模块图 5 流程图分析1. 主函数开始输入顶点个数 n输入边数 e输入选项 a
6、a=1调用insertsort，kruskal 函数a=2输入 v0调用dijkstra，printpath1 函数a=3输入 v0,v1调用dijkstra，printpath2 函数输入 a=4结束图 3.2 主函数流程图2. insertsort 函数 6 开始int i,jfor(i=2;i导入软件中并且运行。3. 对照上述说明运行并检查程序。7 参考文献1王昆仑，李红.数据结构与算法北京：中国铁道出版社，2006 年 5 月2严蔚敏 ，吴伟民. 数据结构 （C 语言版）.清华大学出版社.20073张德富. 算法设计与分析.国防工业出版社.20094朱青. 计算机算法与程序设计.清华大
7、学出版社.20095徐宝文，李志. C 程序设计语言机械工业出版社.20048 附 录（关键部分程序清单）程序代码#includestdio.h #define MAXE 100 struct edges int bv; /起点int tv; /终点int w;/权值 ; typedef struct edges edgeset; int seeks(int set,int v) /顶点集，顶点 v int i; i=v; while(seti0) i=seti; return i; 12 void kruskal(edgeset ge,int n,int e) /边集，顶点数 n，边数 e
8、int setMAXE,v1,v2,i,j,x,y=1; /输入顶点集edgeset xyMAXE;for(i=1;in+1;i+) seti=0; i=1; j=1; printf(第%d 个最小生成树 :n,1);/判断第几个最小生成树while(j=e&i=n-1) v1=seeks(set,gej.bv); /起点v2=seeks(set,gej.tv); /终点if(v1!=v2) xyj=gej;printf(%d,%d):%dn,gej.bv,gej.tv,gej.w); setv1=v2; i+; /计数器（判断顶点数是否溢出） j+; y+;while(gej-1.w=gej
9、.w) /输出所有最小生成树printf(第%d 个最小生成树为:n,y);for(x=1;x=j-2;x+)printf(%d,%d):%dn,xyx.bv,xyx.tv,xyx.w);printf(%d,%d):%dn,gej.bv,gej.tv,gej.w);j+;y+; void insertsort(edgeset ge,int e) /对权值进行排序 int i,j; 13 for(i=2;i=e;i+) if(gei.wgei-1.w) ge0=gei; j=i-1; while(ge0.wgej.w) gej+1=gej; j-; gej+1=ge0; main() edges
10、et geMAXE; int a,n,e,i; printf(请输入顶点个数:); scanf(%d,&n); printf(请输入边的条数:); scanf(%d,&e); printf(请输入边的信息（起点，终点，权值）:n); for(i=1;i=e;i+) scanf(%d,%d,%d,&gei.bv,&gei.tv,&gei.w); printf(在下列菜单中进行选择：n); printf(1.kruskal 算法（起点，终点）权值）：n); printf(2.exit（退出）： n); scanf(%d,&a); while(a!=2) switch(a) case 1:insertsort(ge,e); kruskal(ge,n,e); break; printf(在下列菜单中进行选择：n); printf(1.kruskal 算法（起点，终点）权值）：n); printf(2.exit（退出）： n); scanf(%d,&a); 14 return 1;
