《数据结构课程设计最小生成树Kruskal算法.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计最小生成树Kruskal算法.doc（28页珍藏版）》请在三一办公上搜索。
1、课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目：最小生成树Kruskal算法院（系）：专 业：班 级：学 号：姓 名：指导教师： 目 录1 课程设计介绍11.1 课程设计内容11.2 课程设计要求12 课程设计原理22.1 课设题目粗略分析22.2 原理图介绍42.2.1 功能模块图42.2.2 流程图分析53 数据结构分析113.1 存储结构113.2 算法描述114 调试与分析134.1 调试过程134.2程序执行过程13参考文献16附 录（关键部分程序清单）17 1 课程设计介绍1.1 课程设计内容 编写算法能够建立带权图，并能够用Kruskal算法求该图的最小生成树。
2、最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。1.2 课程设计要求1. 顶点信息用字符串，数据可自行设定。2. 参考相应的资料，独立完成课程设计任务。3. 交规范课程设计报告和软件代码。2 课程设计原理2.1 课设题目粗略分析根据课设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分析：1. 要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。2. Kruskal算法。该算法设置了集合A，该集合一直是某最小生成树的子集。在每步决定
3、是否把边（u,v）添加到集合A中，其添加条件是A（u,v）仍然是最小生成树的子集。我们称这样的边为A的安全边，因为可以安全地把它添加到A中而不会破坏上述条件。3. Dijkstra算法。算法的基本思路是：假设每个点都有一对标号（dj,pj）,其中d是从起源点到点j的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：1） 初始化。起源点设置为：ds=0,ps为空；所有其它点：di=,pi=？；标记起源点s，记k=s，其他所有点设为未标记的。2） k到其直接连接的未标记的点j的距
4、离，并设置： dj=mindj, dk+lkj式中，lkj是从点k到j的直接连接距离。3） 选取下一个点。从所有未标记的结点中，选取dj中最小的一个i： di=mindj, 所有未标记的点j 点i就被选为最短路径中的一点，并设为已标记的。4）找到点i的前一点。从已标记的点中找到直接连接到i的点j*，作为前一点，设置： i=j*5)标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2）再继续。而程序中求两点间最短路径算法。其主要步骤是： 调用dijkstra算法。 将path中的第“终点”元素向上回溯至起点，并显示出来。 2.2 原理图介绍2.2.1 功能模块图开始输入顶点个数n输
5、入边数e输入边集显示菜单，进行选择。求两点间最短距离求两点间最短距离Kruskal算法结束图2.1 功能模块图 2.2.2 流程图分析1. 主函数开始输入顶点个数n输入边数e输入选项aa=1调用insertsort，kruskal函数a=2输入v0调用dijkstra，printpath1函数a=3输入v0,v1调用dijkstra，printpath2函数输入a=4结束 图2.2 主函数流程图2. insertsort函数开始int i,jfor(i=2;i=e;i+)gei.wgei-1.wge0=gei; j=i-1;ge0.wgej.wgej+1=gej; j-;Ygej+1=ge0;
6、NY结束N3. 图2.3 insertsort函数流程图3Kruskal函数开始int setMAXE,v1,v2,i,j;for(i=1;in+1;i+)seti=0; i=1; j=1;j=e&i=n-1v1!=v2v1=seeks(set,gej.bv);v2=seeks(set,gej.tv);printf(%d,%d):%dn,gej.bv,gej.tv,gej.w); setv1=v2; i+;j+;YY结束NN 图2.4 Kruskal函数流程图4. dijkstra函数开始int u,vnum,w,wm;for(w=1;w=n;w+)distw=costv0w; if(cost
7、v0w32767) pathw=v0;vnum=1;vnumn-1wm=32767; u=v0;for(w=1;w=n;w+)if(sw=0&distwwm)u=w;wm=distw;su=1;vnum+;for(w=1;w=n;w+)if(sw=0&distu+costuwdistw&costuw!=32767)distw=distu+costuw;pathw=u;Y结束N 图2.5 dijkstra函数流程图5. printpath1函数开始int i,k;for(i=1;i=n;i+)si=1k=i; while(k!=v0)printf(%d-,k);k=pathk;printf(%d
8、:%dn,k,disti);printf(%d-%d:32767n,i,v0);结束YN 图2.6 printpath1函数流程图 6. printpath2函数开始int k; k=v1;while(k!=v0)printf(%d-,k);k=pathk; printf(%d:%dn,k,distv1);结束 图2.7 printpath2函数流程图3 数据结构分析3.1 存储结构定义一个结构体数组，其空间足够大，可将输入的字符串存于数组中。struct edgesint bv; int tv; int w;3.2 算法描述1. Kruskal函数： 因为Kruskal需要一个有序的边集数组
9、，所以要先对边集数组排序。其次，在执行中需要判断是否构成回路，因此还需另有一个判断函数seeks，在Kruskal中调用seeks。2. dijkstra函数： 因为从一源到其余各点的最短路径共有n-1条，因此可以设一变量vnum作为计数器控制循环。该函数的关键在于dist数组的重新置数。该置数条件是：该顶点是被访问过，并且新起点到该点的权值加上新起点到源点的权值小于该点原权值。因此第一次将其设为：if（sw=0&costuw+distudistw）。但是在实际运行中，发现有些路径的权值为负。经过分析发现，因为在程序中由32767代替。若costuw=32767，那么costuw+distu肯
10、定溢出主负值，因此造成权值出现负值。但是如果costuw=32767，那么distw肯定不需要重新置数。所以将条件改为：if(sw=0&costuw+distudistw&costuw!=32767)。修改之后问题得到解决。3. printpath1函数：该函数主要用来输出源点到其余各点的最短路径。因为在主函数调用该函数前，已经调用了dijkstra函数，所以所需的dist、path、s数组已经由dijkstra函数生成，因此在该函数中，只需用一变量控制循环，一一将path数组中的每一元素回溯至起点即可。其关键在于不同情况下输出形式的不同。4. printpath2函数：该函数主要用来输出两点
11、间的最短路径。其主要部分与printpath1函数相同，只是无需由循环将所有顶点一一输出，只需将path数组中下标为v1的元素回溯至起点并显示出来。4 调试与分析4.1 调试过程在调试程序时主要遇到一下几类问题：1. 有时函数中一些数组中的数据无法存储。2. 对其进行检验发现没有申请空间大小。3. 在源程序的开头用#define定义数值大小，在使用数组时亦可知道它的空间大小。4. 此函数中有时出现负值。5. 对其进行检验发现在程序中由32767代替。若costuw=32767，那么costuw+distu肯定溢出主负值，因此造成权值出现负值。6. 但是当costuw=32767，那么distw
12、肯定不需要重新置数。所以将if（sw=0&costuw+distudistw）改为：if(sw=0&costuw+distu0) i=seti; return i;void kruskal(edgeset ge,int n,int e)int setMAXE,v1,v2,i,j; for(i=1;in+1;i+)seti=0; i=1; j=1;while(j=e&i=n-1)v1=seeks(set,gej.bv); v2=seeks(set,gej.tv); if(v1!=v2)printf(%d,%d):%dn,gej.bv,gej.tv,gej.w); setv1=v2; i+;j+;
13、void insertsort(edgeset ge,int e)int i,j; 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;void dijkstra(int costMAXEMAXE,int distMAXE,int pathMAXE,int sMAXE,int n,int v0)int u,vnum,w,wm; for(w=1;w=n;w+)distw=costv0w; if(costv0w32767) pathw=v0; vnum=1;while(v
14、numn-1)wm=32767; u=v0; for(w=1;w=n;w+) if(sw=0&distwwm)u=w; wm=distw; su=1; vnum+; for(w=1;w=n;w+) if(sw=0&distu+costuwdistw&costuw!=32767)distw=distu+costuw; pathw=u;void printpath1(int dist,int path,int s,int n,int v0)int i,k; for(i=1;i=n;i+) if(si=1)k=i; while(k!=v0) printf(%d-,k); k=pathk; print
15、f(%d:%dn,k,disti); else printf(%d-%d:32767n,i,v0);void printpath2(int dist,int path,int v0,int v1)int k; k=v1;while(k!=v0)printf(%d-,k); k=pathk; printf(%d:%dn,k,distv1);main()edgeset geMAXE; int costMAXEMAXE,distMAXE,pathMAXE,sMAXE,a,n,e,i,j,k,v0,v1; printf(请输入顶点个数:); scanf(%d,&n); printf(请输入边的条数:)
16、; 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.shortpath（终点-起点）：n); printf(3.shortpath between two point（终点-起点）：n); printf(4.exit（退出）：n); scanf(%d,&a);while(a!=4)switch(a)case 1:inse
17、rtsort(ge,e); kruskal(ge,n,e); break;case 2:printf(请输入起始顶点序号:); scanf(%d,&v0); for(i=1;i=n;i+) for(j=1;j=n;j+) costij=32767; for(k=1;k=e;k+) i=gek.bv; j=gek.tv; costij=gek.w; for(i=1;i=n;i+) si=0; sv0=1; dijkstra(cost,dist,path,s,n,v0); printpath1(dist,path,s,n,v0); break;case 3:printf(请输入起始顶点序号:);
18、scanf(%d,&v0); printf(请输入终点序号:); scanf(%d,&v1); for(i=1;i=n;i+) for(j=1;j=n;j+) costij=32767; for(k=1;k=e;k+) i=gek.bv; j=gek.tv; costij=gek.w; for(i=1;i=n;i+) si=0; sv0=1; dijkstra(cost,dist,path,s,n,v0); printpath2(dist,path,v0,v1); break;printf(在下列菜单中进行选择：n);printf(1.kruskal算法（起点，终点）权值）：n);printf
19、(2.shortpath（终点-起点）：n);printf(3.shortpath between two point（终点-起点）：n);printf(4.exit（退出）：n);scanf(%d,&a);return 1;课程设计总结：本次课程设计涉及到的范围很广，让本人能够比较系统的对C语言和数据结构进行一次整理和复习。同时有了很多的体会和经验。1. 巩固了以前学过的C语言的知识，在这次课程设计中我体会到C语言超强的逻辑性，能够熟练使用VC+的编译环境，也对这两门课程有了新的认识，他们既有联系，又相互区别，在编写程序过程中要灵活应用2. 对数据结构的理解有待加强，算法的知识面也有待于提高。不同的人会选择不同的算法，所以即使同样的程序，不同的人必然会设计出不同的方案，所以以后的学习生活中，一定要广泛涉猎，掌握更多更好的解决问题的方法。3. 此次设计让我意识到程序设计是脑力劳动和体力劳动相结合的，没有平时基础的训练是不会写出高效的算法。4. 此次课程设计时间虽短，课设的过程是短暂的，但我所收获的是永恒的。它让我尝到了学习的快乐，成功的喜悦，更让我懂得了不少做人的道理。要完成一项任务或把东西学好就必须有足够的信心，持久的耐心，有面对困难无所畏惧的精神，这对我日后的学习和生活产生了深远一个影响。指导教师评语：指导教师(签字)： 年 月 日课程设计成绩
