课程设计-最小生成树.doc

《课程设计-最小生成树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最小生成树1.任务与需求该课程设计要求从从给定一个地图，包括若干城市间道路的距离，用Prim算法或者Kruskal算法建立最小生成树，求出最小生成树的代价。用邻接矩阵来表示图。根据分析，该课程设计需要完成的具体功能有：(1)能够创建图；(2)为了方便使用，可以把输入的图保存到数据文件中；(3)能够读取数据文件中图的信息，创建图；(4)能够显示最小生成树，包括起始和终点的序号以及最小生成树的代价。图1给定的图2.总体设计对于一个无相连通图G=(V,E)，设G’是它的一个子图，如果G’满足下列条件：(1)G’中包含了G中所有顶点，即V(G’)=V(G)；(2)G’是连通

2、图；(3)G’中无回路。则称G’是G的一棵生成树。如果无相连通图是一个网，那么它的所有生成树中必有一棵边的权值总和最小的生成树，则称这棵生成树是最小代价生成树，简称为最小生成树。最小生成树的概念可以应用到许多实际问题，例如：计算城市之间道路构造问题，要想使总的造价最低，实际上就是寻找该网络的最小生成树。根据任务与需求，该程序需要能够输入数据、保存文件、读取文件、创建图、显示最小生成树。最小生成树的常用算法有两种，分别使用这两种方法进行最小生成树的计算。系统功能模块如图：图2系统功能模块图3.详细设计3.1最小生成树算法常见的两种构造最小生成树的算法是Prim算法和K

3、ruskal算法。1.Prim算法假设G=(V,E)为一网络，其中V为网络中的顶点集合，E为网络中的所有带权边集合。设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，集合T存放G的最小生成树的边。令集合U的初值为U={u0}（假设从u0出发），集合T的初值为T={}。从所有uU，vV-U两个顶点构成的边中，选取具有最小权值的边(u,v)，将顶点v加入集合U中，将边(u,v)加入集合T中。如此不断重复，直到U=V时，最小生成树构造完毕，这时候集合T中包含了最小生成树的所有边。Prim算法描述过程：(1)U={u0}，T={}；(2)while(UV)do(

4、u,v)=min{wuv

5、uU，vV-U}T=T+{u,v}U=U+{v}(3)结束2.Kruskal算法Kruskal算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。它的基本思路是：设无相连通网为G=(V,E)，令G的最小生成树为T，其初态为t=(V,{})，即开始时，最小生成树T由G中的n个顶点构成，顶点之间没有一条边，这样T中各个顶点各自构成一个连通分量。然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。若被考查的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入T中，同时把两个连通分量连接为一个分量；若被考察边的两个顶

6、点属于一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。3.2详细设计在Prim算法中，关键在于集合T的表示，可以设置uSet数组，数组长度为顶点个数，uSet[i]的值为1时，表示顶点i加入集合T中，uSet[i]的值为0时，表示顶点i未加入集合T中，设定一个循环来进行最小生成树的计算，循环开始前将顶点0加入到集合T中，循环结束条件为所有的顶点都已在集合T中。循环体的内容是：遍历所有的边找出权值最小的边，且该条边的两个顶点m和n满足m在集合T中，n不在集合T中，则该边为最小生成树中的一条边，同时将顶点n

7、加入到集合T中。在Kruskal算法中，同样引入一个uSet数组，数组长度为顶点数目，uSet[n]值为m时，说明顶点n在顶点集合m中，最初每个顶点各自为一个连通分量，并分别赋予一个编号，共有顶点数目个连通分量。设定一个循环来进行最小生成树的计算，循环开始前将顶点0加入到集合T中，循环终止条件为所有的顶点均进行了归并，也就是所有顶点都处在同一个连通分量当中。循环体的内容是：遍历所有的边找出权值最小的边，且该条边的两个顶点m和n两个连通分量合并。在实现连通分量合并时，可将m和n的uSet值进行比较，取其小者，并将该值赋予和m或n的uSet值相同的所有顶点，即完成了m和

8、n两个连通分量的合并。4.编码5.测试图3系统界面图4第一条路径信息输入图5把路径信息写入内存图6读出所有路径信息图7Prim算法最小生成树图8Kruskal算法最小生成树图9退出系统