数据结构最小生成树

《数据结构最小生成树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构多元化考核作业题目：最小生成树姓名：卢伟专业班级：物联网工程B1501班学号：目录1课程设计介绍31.1课程设计内容31.2课程设计要求32课程设计原理42.1课设题目粗略分析42.2原理图介绍62.2.1功能模块图62.2.2流程图分析73数据结构分析133.1存储结构133.2算法描述134调试与分析144.1调试过程141.2程序执行过程15参考文献181课程设计介绍1.1课程设计内容编写算法能够建立带权图，并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶

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

3、,v)添加到集合A中，其添加条件是AU{(u,v)}仍然是最小生成树的子集。我们称这样的边为A的安全边，因为可以安全地把它添加到A中而不会破坏上述条件。3.Dijkstra算法。算法的基本思路是：假设每个点都有一对标号(dj,pj)，其中d是从起源点到点j的最短路径的长度(从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；Pj则是从s至町的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：1)初始化。起源点设置为：①ds=o,ps为空；②所有其它点：dj=°°,Pi=?;③标记起源点s,记k二

4、s,其他所有点设为未标记的。2)k到其直接连接的未标记的点j的距离，并设置：dj=min[dj/dk+lkj]式屮，Ikj是从点k到j的直接连接距离。3）选取下一个点。从所有未标记的结点中，选取dj中最小的一个■I:di=min[dj,所有未标记的点j]点i就被选为最短路径中的一点，并设为已标记的。4）找到点i的前一点。从已标记的点屮找到直接连接到i的点j*,作为前一点，设置：i=j*5）标记点i。如果所有点已标记，则算法完全推出，否则，记k二i,转到2）再继续。而程序中求两点间最短路径算法。其主要步骤是：①调用dijkstra

5、算法。②将path中的第“终点”元素向上回溯至起点，并显示出来。2.2原理图介绍2.2.1功能模块图输入顶点个数n输入边数e输入边集一I显示菜单，进行选择。求两点间最短距Kruskal算法求两点间最短距图2.1功能模块图2.2.2流程图分析1.主函数输入a=4（结束）丿图2.2主函数流程图2.insertsort函数开始inti,j3.Kruskal函数intset[MAXE],vl,v2Jj;Jfor(i=l;i

6、w<=n;w++){dist[w]=cost[vO][w];if(cost[v0][w]<32767)path[w]=vO;}vnum=l;Nwm=32767;u=vO;for(w=l;w<=n;w++)if(s[w]==O&&dist[w]

7、=u;}5.printpathl函数(开始)/inti,k;printf("%d<-%d:32767XnMvO);k=i;while(k!=vO){printf(M%d<-",k);k=path[k];}printf(M%d:%dn,k,dist[i]);图2.6printpathl函数流程图三一:>zp、>l=三p罠p%=七u匸d六swdu兰上叮vpf=七u=d)oahmo-zm辛亠空iu一「彖比一擦冈z£edlu一」d.93数据结构分析3.1存储结构定义一个结构体数组，其空间足够大，可将输入的字符串存于数组中。stru

8、ctedges{intbv;inttv;intw;}；3.2算法描述1.Kruskal函数:因为Kruskal需要一个有序的边集数组，所以要先对边集数组排序。其次，在执行中需耍判断是否构成回路，因此还需另有一个判断函数seeks,在Kruskal中调用seeks