克鲁斯卡尔最小生成树解析

《克鲁斯卡尔最小生成树解析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计报告构造可以使n个城市连接的最小生成树课程名称：《数据结构与算法》课程设计院（系）：信息科学与技术学院专业班级：学号：姓名：指导老师：17目录一需求分析31.1问题描述：31.2功能要求：3二概要设计3三详细设计33.1数据类型定义33.2程序的主要函数43.3克鲁斯卡尔算法思想描述43.4克鲁斯卡尔算法设计5四测试分析5五心得体会8附录：程序源代码817一、需求分析1.1问题描述给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。1.2功能要

2、求城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。城市间的距离以邻接矩阵的方式输入（要求至少6个城市，10条边）。二、概要设计2.1该程序的主要功能：能实现根据输入城市的信息可以判断该城市间的距离网是否构成最小生成树，遍历城市生成最小生成树，通过计算得到最小生成树的代价。2.2该城市间的距离网用邻接矩阵表示。并且把2个城市的看成起点和

3、终点，城市之间的距离看成边，并以此设计结构体。定义结构体数组，，将输入的矩阵转化为相对应的结构体来存储城市与城市直接的关系2.3先用judge()判断能否生成是否为联通图，再用克鲁斯卡尔（Kruskal）算法将输入的矩阵生立最小生成树，打印出来。创建用邻接矩阵表示的城市道路网输入城市数道路权值判断是否可以连通Krushal算法，并将所到的结果输出退出17三、详细设计3.1数据类型定义typedefstructnode/*构造一个结构体*/{intstr;/*起点*/intend;/*终点*/intdis;/*距离

4、*/}node;为了用邻接矩阵表示图G，先是定义二维数组的每一个元素含道路值然后在图的定义中定义一个此二维数组的结构成员。并且在图中还定义一个用来存放城市的一维数组及int型的城市数级道路数。用二维数组的两个下标表示道路，这两个下标又在一位数组中对应两个城市，这样就建立起了一个城市到城市之间的邻接矩阵。将该邻接矩阵转化为图示的结构体，用于计算。3.2程序的主要函数能实现根据输入城市的信息可以判断出该城市间的距离网是否构成最小生成树，遍历城市生成最小生成树，通过计算得到最小生成树的代价主要函数：a)intmenu(

5、)菜单函数，给用户提示信息，让用户选择相应功能。b)voidcreate()输入城市信息函数，将用户输入的邻接矩阵以二维数组的形式存放到内存中，为Krushal()服务c)voidjudge()判断用户输入的邻接矩阵所转化的图是否可以生成最小生成树d)voidfind()判断当前是否构成回路的函数e)voidUnion()将能构成最小生成树的边添加到一个集合，f）voidKrushal()克鲁斯算法求最小生成树173.3克鲁斯卡尔算法思想基本描述：假设连通图N=（V，{E}），则令最小生成树的初始状态为只有n顶点

6、而无边的非连通图T=(V,{})，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一个连通分量上为止3.4克鲁斯卡尔算法设计a.设置计数器E，初值为0，记录已选中的边数。将所有边从小到大排序，存于p[]中。b.从p[]中选择一条权值最小的边，检查其加入到最小生成树中是否会构成回路，若是，则此边不加入生成树；否则，加入到生成树中，计数器E累加1。c.从E中删除此最小边，转b继续执

7、行，直到k=n-1,算法结束d.判断是否构成回路的方法：设置集合S，其中存放已加入到生成树中的边所连接的顶点集合，当一条新的边要加入到生成树中时，检查此边所连接的两个顶点是否都已经在S中，若是，则表示构成回路，否则，若有一个顶点不在S中或者两个顶点都不在S中，则不够成回路。四、测试分析以一个6个城市、10条边的网络图为例进行测试171系统界面：172输入信息设置两顶点之间无边时∞权值为100003数据处理(1)、判断能否构成最小生成树（2）、遍历所有城市生成最小生成数17（3）、退出五、体会心得通过本周的课程设计

8、，终于圆满完成了课程设计的任务，我也有不少收获。既巩固和加深了对数据结构的理解，认识到《数据结构》是计算机专业一门重要的专业技术基础课程，还提高了我综合运用本课程所学知识的能力。而且，并不是单纯的看看教材就能解决我们的实际问题，所以还要去查找各种我们所需要的资料，所以这次课程设计也培养了我选用参考书，查阅手册及文献资料的能力。要完成一个课程设计的课题并不是一次就能编译成功