数据结构课程设计报告最小生成树kruskal算法【最新】

《数据结构课程设计报告最小生成树kruskal算法【最新】》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、合肥学院计算机科学与技术系课程设计报告2014-2015学年第二学期课程数据结构课程设计名称Kruskal算法求最小生成树学生姓名姚国栋学号1204091021专业班级12软件工程指导教师何立新2014年9月68题目：设计程序完成如下功能：对给定过的网和起点，用kruskal算法的基本思想求解其所有的最小生成树1、问题分析和任务定义根据课设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分析：要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程

2、。Kruskal算法。该算法设置了集合A，该集合一直是某最小生成树的子集。在每步决定是否把边（u,v）添加到集合A中，其添加条件是A∪{（u,v）}仍然是最小生成树的子集。我们称这样的边为A的安全边，因为可以安全地把它添加到A中而不会破坏上述条件。2数据结构的选择和概要设计存储结构定义一个结构体数组，其空间足够大，可将输入的字符串存于数组中。structedges{intbv;inttv;intw;};概要设计。算法思想 ：68算法会先按照权重的非递减顺序对图中的边进行排序。然后从一个空子图开始，扫描这个有序表，试图把列表中的下一条边加到当前的子图中。当然，这种添加

3、不应导致一个回路，如果产生回路，就把这条边跳过。当图的所有顶点都包含在所构造的树中以后，算法停止。算法的基本思路是：Kruskal算法每次选择n-1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。Kruskal算法分e步，其中e是网络中边的数目。按耗费递增的顺序来考虑这e条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。假设每个点都有一对标号（dj,pj）,其中d是从起源点到点j的最短路径的长度（从顶点到其本身的

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

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

6、printpath1函数a=3输入v0,v1调用dijkstra，printpath2函数输入a=4结束图3.2主函数流程图2.insertsort函数68开始inti,jfor(i=2;i<=e;i++)ge[i].w

7、e&&i<=n-1v1!=v2v1=seeks(set,ge[j].bv);v2=seeks(set,ge[j].tv);printf("(%d,%d):%d",ge[j].bv,ge[j].tv,ge[j].w);set[v1]=v2;i++;j++;YY结束NN图3.4Kruskal函数流程图684上机调试过程调试过程在调试程序时主要遇到一下几类问题：1.有时函数中一些数组中的数据无法存储。2.对其进行检验发现没有申请空间大小。3.在源程序的开头用#define定义数值大小，在使用数组时亦可知道它的空间大小。4.此函数中有时出现负值。5.对其进行检验发现