数据结构课程设计最小生成树Kruskal算法

1、课课 程程 设设 计计 报报 告告课程设计名称：数据结构课程设计数据结构课程设计课程设计题目：最小生成树 kruskal 算法院（系）：专 业：班 级：学 号：姓 名：指导教师： i 目目 录录1 1 课程设计介绍课程设计介绍.11.1 课程设计内容.11.2 课程设计要求.12 2 课程设计原理课程设计原理.22.1 课设题目粗略分析.22.2 原理图介绍.42.2.1 功能模块图.42.2.2 流程图分析.53 数据结构分析数据结构分析.113.1 存储结构.113.2 算法描述.114 4 调试与分析调试与分析.134.1 调试过程.134.2 程序执行过程.13参考文献参考文献.16附

2、附 录（录（关关键部分程序清单）键部分程序清单）.17 1 1 1 课程设计介绍课程设计介绍1.11.1 课程设计内容课程设计内容 编写算法能够建立带权图，并能够用 kruskal 算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。1.21.2 课程设计要求课程设计要求1. 顶点信息用字符串，数据可自行设定。2. 参考相应的资料，独立完成课程设计任务。3. 交规范课程设计报告和软件代码。 2 2 2 课程设计原理课程设计原理2.12.1 课设题目粗略分析课设题目粗略分析根据课设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分

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

4、是零路（没有弧的路） ，其长度等于零） ；pj则是从 s 到j 的最短路径中 j 点的前一点。求解从起源点 s 到点 j 的最短路径算法的基本过程如下：1）初始化。起源点设置为：ds=0,ps为空；所有其它点：di=,pi=？；标记起源点 s，记 k=s，其他所有点设为未标记的。2）k 到其直接连接的未标记的点 j 的距离，并设置： dj=mindj, dk+lkj 3 式中，lkj是从点 k 到 j 的直接连接距离。3）选取下一个点。从所有未标记的结点中，选取 dj中最小的一个 i： di=mindj, 所有未标记的点 j 点 i 就被选为最短路径中的一点，并设为已标记的。4）找到点 i 的

5、前一点。从已标记的点中找到直接连接到 i 的点 j*，作为前一点，设置： i=j*5)标记点 i。如果所有点已标记，则算法完全推出，否则，记 k=i，转到 2）再继续。而程序中求两点间最短路径算法。其主要步骤是： 调用 dijkstra 算法。将 path 中的第“终点”元素向上回溯至起点，并显示出来。 4 2.22.2 原理图介绍原理图介绍2.2.12.2.1 功能模块图功能模块图开始开始输入顶点个数 n输入边数 e输入边集显示菜单，进行选择。求两点间最短距离求两点间最短距离kruskal算法结束结束图 2.1 功能模块图 5 2.2.2 流程图分析流程图分析1. 主函数开始开始输入顶点个数

6、 n输入边数 e输入选项 aa=1调用insertsort，kruskal 函数a=2输入 v0调用dijkstra，printpath1 函数a=3输入 v0,v1调用dijkstra，printpath2 函数输入 a=4结束结束 图 2.2 主函数流程图2. insertsort 函数 6 开始开始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;ny结束结束n3. 图 2.3 insertsort 函数流程图 7 3kruskal 函数开始开始int setmaxe,v

7、1,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 函数流程图 8 4. dijkstra 函数开始开始int u,vnum,w,wm;for(w=1;w=n;w+)distw=costv0w; if(costv0w32767) pathw=v0;vnum=1;vnumn-1wm=32767;

8、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 函数流程图 9 5. printpath1 函数开始开始int i,k;for(i=1;i=n;i+)si=1k=i; while(k!=v0)printf(%d-,k);k=pathk;printf(%d:%dn,k,disti);printf(%d-%d:32767n

9、,i,v0);结束结束yn 图 2.6 printpath1 函数流程图 10 6. printpath2 函数开始开始int k; k=v1;while(k!=v0)printf(%d-,k);k=pathk; printf(%d:%dn,k,distv1);结束结束 图 2.7 printpath2 函数流程图 11 3 数据结构分析数据结构分析3.13.1 存储结构存储结构定义一个结构体数组，其空间足够大，可将输入的字符串存于数组中。struct edgesint bv; int tv; int w;3.23.2 算法描述算法描述1. kruskal 函数： 因为 kruskal 需要一

10、个有序的边集数组，所以要先对边集数组排序。其次，在执行中需要判断是否构成回路，因此还需另有一个判断函数 seeks，在 kruskal 中调用 seeks。2. dijkstra 函数： 因为从一源到其余各点的最短路径共有 n-1 条，因此可以设一变量 vnum 作为计数器控制循环。该函数的关键在于 dist 数组的重新置数。该置数条件是：该顶点是被访问过，并且新起点到该点的权值加上新起点到源点的权值小于该点原权值。因此第一次将其设为： 12 if（sw=0&costuw+distudistw） 。但是在实际运行中，发现有些路径的权值为负。经过分析发现，因为在程序中由 32767 代替。若 c

11、ostuw=32767，那么 costuw+distu肯定溢出主负值，因此造成权值出现负值。但是如果 costuw=32767，那么 distw肯定不需要重新置数。所以将条件改为：if(sw=0&costuw+distudistw&costuw!=32767)。修改之后问题得到解决。3. printpath1 函数：该函数主要用来输出源点到其余各点的最短路径。因为在主函数调用该函数前，已经调用了 dijkstra 函数，所以所需的dist、path、s 数组已经由 dijkstra 函数生成，因此在该函数中，只需用一变量控制循环，一一将 path 数组中的每一元素回溯至起点即可。其关键在于不同

12、情况下输出形式的不同。4. printpath2 函数：该函数主要用来输出两点间的最短路径。其主要部分与 printpath1 函数相同，只是无需由循环将所有顶点一一输出，只需将 path 数组中下标为 v1 的元素回溯至起点并显示出来。 13 4 4 调试与分析调试与分析4.14.1 调试过程调试过程在调试程序时主要遇到一下几类问题：1. 有时函数中一些数组中的数据无法存储。2. 对其进行检验发现没有申请空间大小。3. 在源程序的开头用#define 定义数值大小，在使用数组时亦可知道它的空间大小。4. 此函数中有时出现负值。5. 对其进行检验发现在程序中由 32767 代替。若 costu

13、w=32767，那么 costuw+distu肯定溢出主负值，因此造成权值出现负值。6. 但是当 costuw=32767，那么 distw肯定不需要重新置数。所以将 if（sw=0&costuw+distudistw）改为：if(sw=0&costuw+distu0) i=seti; return i;void kruskal(edgeset ge,int n,int e) 18 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,

14、gej.tv); if(v1!=v2)printf(%d,%d):%dn,gej.bv,gej.tv,gej.w); setv1=v2; i+;j+;void insertsort(edgeset ge,int e) 19 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,vnu

15、m,w,wm; for(w=1;w=n;w+)distw=costv0w; 20 if(costv0w32767) pathw=v0; vnum=1;while(vnumn-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; 21 void printpath1(int dist,int path,int s,int n,i

16、nt v0)int i,k; for(i=1;i=n;i+) if(si=1)k=i; while(k!=v0) printf(%d-,k); k=pathk; printf(%d:%dn,k,disti); else printf(%d-%d:32767n,i,v0);void printpath2(int dist,int path,int v0,int v1) 22 int k; k=v1;while(k!=v0)printf(%d-,k); k=pathk; printf(%d:%dn,k,distv1);main()edgeset gemaxe; int costmaxemaxe,d

17、istmaxe,pathmaxe,smaxe,a,n,e,i,j,k,v0,v1; printf(请输入顶点个数:); scanf(%d,&n); printf(请输入边的条数:); scanf(%d,&e); printf(请输入边的信息（起点，终点，权值）:n); 23 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 b

18、etween two point（终点-起点）：n); printf(4.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=1;i=n;i+) for(j=1;j=n;j+) costij=32767; for(k=1;k=e;k+) 24 i=gek.bv; j=gek.tv; costij=gek.w; for(i=1;i=n;i+) si=0; sv0=1;

19、 dijkstra(cost,dist,path,s,n,v0); printpath1(dist,path,s,n,v0); break;case 3:printf(请输入起始顶点序号:); 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; 25 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);