2022年最小生成树Kruskal算法参照 .pdf
《2022年最小生成树Kruskal算法参照 .pdf》由会员分享,可在线阅读,更多相关《2022年最小生成树Kruskal算法参照 .pdf(28页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、课 程 设 计 报 告课程设计名称:数据结构课程设计课程设计题目:最小生成树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附录(关键部
2、分程序清单).17名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页,共 28 页 -1 1 课程设计介绍1.1 课程设计内容编写算法能够建立带权图,并能够用Kruskal 算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。1.2 课程设计要求1.顶点信息用字符串,数据可自行设定。2.参考相应的资料,独立完成课程设计任务。3.交规范课程设计报告和软件代码。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页,共 28 页 -2 2 课程设计原理2.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 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页,共 28 页 -3 式中,lkj是从点 k 到 j 的直接连接距离。3)选取下一个点。从所有未标记的结点中,选取dj中最小的一个 i:di=mindj,所有未标记的点 j 点 i 就被选为最
5、短路径中的一点,并设为已标记的。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、师资料总结-精品资料欢迎下载-名师精心整理-第 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;
7、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+
8、;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)dis
9、tw=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 printpat
10、h2 函数流程图开始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.dijkstr
11、a 函数:因为从一源到其余各点的最短路径共有n-1 条,因此可以设一变量 vnum 作为计数器控制循环。该函数的关键在于dist 数组的重新置数。该置数条件是:该顶点是被访问过,并且新起点到该点的权值加上新起点到源点的权值小于该点原权值。因此第一次将其设为:if(sw=0&costuw+distudistw)。但是在实际运行中,发现有名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页,共 28 页 -12 些路径的权值为负。经过分析发现,因为在程序中由32767代替。若 costuw=32767,那么 costuw+distu 肯定溢出主负值,因此造成权值出现负值。但是如果costuw
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年最小生成树Kruskal算法参照 2022 最小 生成 Kruskal 算法 参照
限制150内