最小生成树Kruskal算法.doc

《最小生成树Kruskal算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、...课程设计报告课程设计名称：数据结构课程设计课程设计题目：最小生成树Kruskal算法院（系）：专业：班级：学号：姓名：指导教师：.......目录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.......1课程设计介绍1.1课程设计容编写算法能够建立带权图，并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上

2、的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。1.2课程设计要求1.顶点信息用字符串，数据可自行设定。2.参考相应的资料，独立完成课程设计任务。3.交规课程设计报告和软件代码。.......2课程设计原理2.1课设题目粗略分析根据课设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分析：1.要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。2.Kruskal算法。该算法设置了集合A，该集合一直是某最小生成树的子集。在每步决定是否把边（u,v）添

3、加到集合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的距离，并

4、设置：.......dj=min[dj,dk+lkj]式中，lkj是从点k到j的直接连接距离。1）选取下一个点。从所有未标记的结点中，选取dj中最小的一个i：di=min[dj,所有未标记的点j]点i就被选为最短路径中的一点，并设为已标记的。4）找到点i的前一点。从已标记的点中找到直接连接到i的点j*，作为前一点，设置：i=j*5)标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2）再继续。而程序中求两点间最短路径算法。其主要步骤是：①调用dijkstra算法。②将path中的第“终点”元素向上回溯至起点，并显示出来。.......2.2原理图介绍2.2.1功能模块图开始

5、输入顶点个数n输入边数e输入边集显示菜单，进行选择。求两点间最短距离求两点间最短距离Kruskal算法结束图2.1功能模块图.......2.2.2流程图分析1.主函数开始输入顶点个数n输入边数e输入选项aa=1调用insertsort，kruskal函数a=2输入v0调用dijkstra，printpath1函数a=3输入v0,v1调用dijkstra，printpath2函数输入a=4结束图2.2主函数流程图2.insertsort函数.......开始inti,jfor(i=2;i<=e;i++)ge[i].w

6、ge[j].wge[j+1]=ge[j];j--;Yge[j+1]=ge[0];NY结束N1.图2.3insertsort函数流程图.......3．Kruskal函数开始intset[MAXE],v1,v2,i,j;for(i=1;i

7、图.......4.dijkstra函数开始intu,vnum,w,wm;for(w=1;w<=n;w++){dist[w]=cost[v0][w];if(cost[v0][w]<32767)path[w]=v0;}vnum=1;vnum