Kruskal算法实现-数据结构报告.docx

《Kruskal算法实现-数据结构报告.docx》由会员分享，可在线阅读，更多相关《Kruskal算法实现-数据结构报告.docx（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、河南工程学院数据结构与算法课程设计成果报告Kruskal算法实现2014年12月29日错误!未指定书签。for(i=2;i=e;i+) if (gei. wgei-l. w) (ge0=gei;j 二 iT；while(ge0j. wgej. w)(gej+l=gej;尸；gej+l=ge0;)void dijkstra(int costMAXEMAXE, int distMAXE, int pathMAXE, int sMAXE, int n, int vO)(int u, vnum, w, wm;for(w=l;w=n;w+)(distw=costvOw;if(costvOw32767)p

2、athw=v0;)vnum=l;while(vnumn-l)(wm=32767;u 二 vO;for (w=l;w=n;w+)if(sw=0&distwwm) (u=w;wm=distw;)su=l;vnum+;for(w=l;w=n;w+)if (sw=0&distu+cost u wdistw&costu w !=32767)distw=distu+costuw; pathw=u;错误!未指定书签。)void printpathl(int dist, int path, int s,int n,int vO) (int i, k;for(i=l;i=n;i+)if (si=l)(k=i;w

3、hile (k!=vO)(printf(%d-，k);k=pathk;)printf(%d:%dn，k,disti);elseprintf(，%d-%d:32767n，/, i, vO);void printpath2 (int dist, int path, int vO, int vl) (int k;k=vl;while (k!=vO)(printfk);k=pathk;printf (，%d:%dn/，, k, distvl);)main ()(edgeset geMAXE;int costMAXEMAXE, distMAXE, pathMAXE, sMAXE, a, n, e, i,

4、 j, k, vO, vl; printf (请输入顶点个数:“)；scanf(d，&n);printf (请输入边的条数:)；scanf(%d,&e);printf (请输入边的信息(起点，终点，权值)：n)；for(i=l;i=e;i+)错误!未指定书签。scanf (d, %d, %d，&gei. bv, &gei. tv, &gei. w);printf (在以下菜单中进行选择：n);printf (L kruskal 算法(起点，终点)权值)：n)；printf (z，2. shortpath (终点一起点)：n)；printf (z，3. shortpath between two

5、 point (终点一起点)：n);printf (，z4. exit (退出)：n);scanf(%d, &a);while(a!=4)switch(a)case 1:insertsort (ge,e);kruskal (ge,n,e);break;case 2: printf (”请输入起始顶点序号:);scanf(d”, &v0);for (i=l;i=n;i+)for(j=l;j=n;j+)costij=32767;for (k=l;k=e;k+) i=gek. bv;j=gek. tv;costij=gek. w;for (i=l;i=n;i+)si=0;s vO=l;di jkst

6、ra(cost, dist, path, s, n, vO);printpathl (dist, path, s, n, vO);break;case 3: printf (请输入起始顶点序号:);scanf(d，&v0);printf (请输入终点序号:)； scanf(d，&vl);for (i=l;i=n;i+)for(j=l;j=n;j+)costi j=32767;for(k=l;k=e;k+)i=gek. bv;错误!未指定书签。j=gek. tv;costij=gek. w;)for (i=l;iy cost: z其中表示节点x与y间有一条边，权值为zl-2cost:5 2-3c

7、ost:1 2-5cost:3 35cost:2 l-7cost:2 4-7cost:34-5cost:6 8-9cost:1 7-9cost:9 6-9cost:2 3-9cost:8 7-6cost:38-7cost:4 3-6cost:7 5-7cost:10 l-4cost:6 1-3cost:7 5-8cost:39-10cost:5 8-10cost:3 5-7cost:10其中，顶点数为10,边数为20。11错误!未指定书签。4. 2测试结果分析上述测试数据表达在代码中为：edge e = (l,3,2), (1,2,4) (3,2,1), (2,5, 5), (3, 5,6);

8、kruskal test (5, 4, e);couttest. solve ()endl;所构成的图如图4. 2所示：图4. 2中蓝色的边构成最小生成树，总和为2012错误!未指定书签。5总结本次课程设计涉及到的范围很广，让本人能够比拟系统的对c语言和数据结 构进行一次整理和复习。同时有了很多的体会和经验。1 .巩固了以前学过的c语言的知识,在这次课程设计中我体会到C语言超强 的逻辑性，能够熟练使用VC+的编译环境，也对这两门课程有了新的认识，他们 既有联系，又相互区别，在编写程序过程中要灵活应用2 .对数据结构的理解有待加强，算法的知识面也有待于提高。不同的人会选 择不同的算法，所以即使同

9、样的程序，不同的人必然会设计出不同的方案，所以 以后的学习生活中，一定要广泛涉猎，掌握更多更好的解决问题的方法。3 .此次设计让我意识到程序设计是脑力劳动和体力劳动相结合的，没有平时 基础的训练是不会写出高效的算法。此次课程设计时间虽短，课设的过程是短暂的，但我所收获的是永恒的。它 让我尝到了学习的快乐，成功的喜悦，更让我懂得了不少做人的道理。要完成一 项任务或把东西学好就必须有足够的信心，持久的耐心，有面对困难无所畏惧的 精神，这对我日后的学习和生活产生了深远一个影响。13错误!未指定书签。参考文献1数据结构（C语言版）.严蔚敏,吴伟民.清华大学出版社.20072算法设计与分析.张德富.国防

10、工业出版社.20093计算机算法与程序设计.朱青.清华大学出版社.20094C程序设计语言.徐宝文，李志.机械工业出版社.20041415错误!未指定书签。题目Kruskal算法实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答以下问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:1课程设计目标11.1课程

11、设计目标11. 2课程设计任务12分析与设计21.1 题目需求分析22. 2存储结构设计23. 3算法描述34. 4程序流程图45. 5测试程序说明53程序清单64测试114.1测试数据114. 2测试结果分析125总结13参考文献14错误!未指定书签。1课程设计目标与任务1.1 课程设计目标了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能 力。2 .初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方 法和技能。3 .提高综合运用所学的理论知识和方法独立分析和解决问题的能力,增强理 论与实践相结合的技巧。4 .训练用系统的观点和软件开发一般规范进行软件开发，培养软件

12、工作者所 应具备的科学的工作方法和作风。5 .初步了解软件开发的一般过程，培养学习热情以及加强自主学习。6 .训练自己动手分析，解决问题的能力，掌握调试程序，排查错误的常用技 巧。7 .增强动手能力，学会结合实际解决问题。1. 2课程设计任务1 .对给定的图结构，用KRUSKAL算法基本思想求解出所有最小生成树2 .最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形 方式显示出来，将复杂的运行过程以动态方式显示出来3 .给出假设干例程，演示通过调用自己所缩写程序来实现相关问题的求解错误!未指定书签。2分析与设计3.1 题目需求分析根据课设题目要求，拟将整体程序分为三大模块。以下是三

13、个模块的大体分 析：1. 要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操 作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点 和权值）和邻接矩阵比拟方便以后的编程。2. Kruskal算法。该算法设置了集合A,该集合一直是某最小生成树的子集。 在每步决定是否把边（u,v）添加到集合A中，其添加条件是AU （u,v） 仍然 是最小生成树的子集。我们称这样的边为A的平安边，因为可以平安地把它添加 到A中而不会破坏上述条件。3. Dijkstra算法。算法的基本思路是：假设每个点都有一对标号（&,0）， 其中d是从起源点到点j的最短路径的长度（从顶点到其本身的最短

14、路径是零路 （没有弧的路），其长度等于零）；Pj那么是从s到j的最短路径中j点的前一点。2. 2存储结构设计定义一个结构体数组，其空间足够大，可将输入的字符串存于数组中。struct edgesint bv;int tv;int w;）；错误!未指定书签。2. 3算法描述1. Kruskal函数： 因为Kruskal需要一个有序的边集数组，所以要先对边 集数组排序。其次，在执行中需要判断是否构成回路，因此还需另有一个判断函 数 seeks,在 Kruskal 中调用 seeks。2. dijkstra函数：因为从一源到其余各点的最短路径共有n-1条，因此可 以设一变量vnum作为计数器控制循环

15、。该函数的关键在于dist数组的重新置数。 该置数条件是：该顶点是被访问过，并且新起点到该点的权值加上新起点到源点 的权值小于该点原权值。因此第一次将其设为：if(sw=0&costuw+distudistw)。3. printpathl函数：该函数主要用来输出源点到其余各点的最短路径。因 为在主函数调用该函数前，已经调用了 dijkstra函数，所以所需的dist、path、 s数组已经由dijkstra函数生成，因此在该函数中，只需用一变量控制循环，一 一将path数组中的每一元素回溯至起点即可。其关键在于不同情况下输出形式的 不同。4. printpath2函数：该函数主要用来输出两点间

16、的最短路径。其主要局部 与printpathl函数相同，只是无需由循环将所有顶点一一输出，只需将path数 组中下标为vl的元素回溯至起点并显示出来。错误!未指定书签。2.4程序流程图程序以kruskal类实现求最小生成树。构造函数接受3个参数，分别是顶点 个数，边数，和选项。/输入a=4图2.4主函数流程图错误!未指定书签。2. 5测试程序说明在测试程序时主要遇到一下几类问题：1 .有时函数中一些数组中的数据无法存储。2 .对其进行检验发现没有申请空间大小。3 .在源程序的开头用#define定义数值大小，在使用数组时亦可知道它的空 间大小。4 .此函数中有时出现负值。5 .对其进行检验发现

17、在程序中8由32767代替。假设costuw=32767,那 么cost u w+distu肯定溢出主负值，因此造成权值出现负值。6 .但是当costuw =32767,那么distw肯定不需要重新置数。所以将 if (sw=0&cost u w+dist udist w)改为：if (s w -0&cost u w +dist u 0)i=set i;return i;void kruskal (edgeset ge, int n, int e)(int setMAXE,vl,v2, i,j;for(i=l;in+l;i+)seti=0;i=l；J-l；while(j=e&i=n-l)(vl二seeks (set,gej.bv);v2=seeks(set,gej.tv);if(vl!=v2)(printf (，z(%d, %d) :%dn”, gej. bv, gej. tv, gej. w);setvl=v2;i+；)j+；)void insertsort (edgeset ge, int e)int i, j;