2022年最小生成树Kruskal算法参照 .pdf

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