《geuAAA最小生成树Kruskal算法》由会员分享，可在线阅读，更多相关《geuAAA最小生成树Kruskal算法（28页珍藏版）》请在金锄头文库上搜索。
1、课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目：最小生成树 Kruskal 算法 院（系）： 专 业： 班 级： 学 号： 姓 名： 指导教师： 目目 录录 1 1 课程设计介绍课程设计介绍 .1 1 1.1 课程设计内容.1 1.2 课程设计要求.1 2 2 课程设计原理课程设计原理 .2 2 2.1 课设题目粗略分析.2 2.2 原理图介绍.4 2.2.1 功能模块图.4 2.2.2 流程图分析.5 3 3 数据结构分析数据结构分析 .1111 3.1 存储结构.11 3.2 算法描述.11 4 4 调试与分析调试与分析 .1313 4.1
2、 调试过程.13 4.2 程序执行过程.13 参考文献参考文献 .1616 附附 录（录（关关键部分程序清单）键部分程序清单） .1717 1 1 课程设计介绍课程设计介绍 1.11.1 课程设计内容课程设计内容 编写算法能够建立带权图，并能够用 Kruskal 算法求该图的 最小生成树。最小生成树能够选择图上的任意一点做根结点。最 小生成树输出采用顶点集合和边的集合的形式。 1.21.2 课程设计要求课程设计要求 1. 顶点信息用字符串，数据可自行设定。 2. 参考相应的资料，独立完成课程设计任务。 3. 交规范课程设计报告和软件代码。 2 2 课程设计原理课程设计原理 2.12.1 课设题
3、目粗略分析课设题目粗略分析 根据课设题目要求，拟将整体程序分为三大模块。以下是三个模 块的大体分析： 1. 要确定图的存储形式，通过对题目要求的具体分析。发现该题 的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构 体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。 2. Kruskal 算法。该算法设置了集合 A，该集合一直是某最小生 成树的子集。在每步决定是否把边（u,v）添加到集合 A 中，其添加 条件是 A（u,v）仍然是最小生成树的子集。我们称这样的边为 A 的安全边，因为可以安全地把它添加到 A 中而不会破坏上述条件。 3. Dijkstra 算法。算法的基本思路是
4、：假设每个点都有一对标 号（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 式中，lkj是从点 k 到 j 的直接连接距离。 3）选取下一个点。从所有未标记的结点中，选取 dj中最
5、小的一个 i： di=mindj, 所有未标记的点 j 点 i 就被选为最短路径中的一点，并设为已标记的。 4）找到点 i 的前一点。从已标记的点中找到直接连接到 i 的点 j*， 作为前一点，设置： i=j* 5)标记点 i。如果所有点已标记，则算法完全推出，否则，记 k=i， 转到 2）再继续。 而程序中求两点间最短路径算法。其主要步骤是： 调用 dijkstra 算法。 将 path 中的第“终点”元素向上回溯至起点，并显示出 来。 2.22.2 原理图介绍原理图介绍 2.2.12.2.1 功能模块图功能模块图 开始开始 输入顶点个数 n 输入边数 e 输入边集 显示菜单，进行 选择。
6、求两点间最短距 离 求两点间最短距 离 Kruskal算法 结束结束 图 2.1 功能模块图 2.2.22.2.2 流程图分析流程图分析 1. 主函数 开始开始 输入顶点个数 n 输入边数 e 输入选项 a a=1 调用 insertsort，krus kal 函数 a=2 输入 v0 调用 dijkstra，printp ath1 函数 a=3 输入 v0,v1 调用 dijkstra，printpa th2 函数 输入 a=4 结束结束 图 2.2 主函数流程图 2. insertsort 函数 开始开始 int i,j for(i=2;i=e;i+) gei.w gei- 1.w ge0
7、=gei; j=i-1; ge0. wgej .w gej+1=gej; j-; Y gej+1=ge0; N Y 结束结束 N 3. 图 2.3 insertsort 函数流程图 3Kruskal 函数 开始开始 int setMAXE,v1,v2,i,j; for(i=1;in+1;i+) seti=0; i=1; j=1; j=e v2=seeks(set,gej.tv); printf(%d,%d):%dn,gej.bv,g ej.tv,gej.w); setv1=v2; i+; j+; Y Y 结束结束 N N 图 2.4 Kruskal 函数流程图 4. dijkstra 函数 开
8、始开始 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=0wm=distw; su=1;vnum+; for(w=1;w=n;w+) if(sw=0pathw=u; Y 结束结束 N 图 2.5 dijkstra 函数流程图 5. printpath1 函数 开始开始 int i,k; for(i=1;i=n;i+) si=1 k=i; while(k!=v0) printf(%d-,k)
9、; k=pathk; printf(%d:%dn,k,disti); printf(%d- %d:32767n,i,v0); 结束结束 Y N 图 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 数据结构分析数据结构分析 3.13.1 存储结构存储结构 定义一个结构体数组，其空间足够大，可将输入的字符串存于数组中。 struct edges int
10、 bv; int tv; int w; ; 3.23.2 算法描述算法描述 1. Kruskal 函数： 因为 Kruskal 需要一个有序的边集数组，所以要先对边集数 组排序。其次，在执行中需要判断是否构成回路，因此还需另有一个 判断函数 seeks，在 Kruskal 中调用 seeks。 2. dijkstra 函数： 因为从一源到其余各点的最短路径共有 n-1 条，因此可以设 一变量 vnum 作为计数器控制循环。该函数的关键在于 dist 数组的重 新置数。该置数条件是：该顶点是被访问过，并且新起点到该点的权 值加上新起点到源点的权值小于该点原权值。因此第一次将其设为： if（sw=
11、0 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 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) 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 pa
