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

最小生成树1. 任务与需求该课程设计要求从从给定一个地图，包括若干城市间道路的距离，用Prim算法或者Kruskal算法建立最小生成树，求出最小生成树的代价。用邻接矩阵来表示图。根据分析，该课程设计需要完成的具体功能有：(1) 能够创建图；(2) 为了方便使用，可以把输入的图保存到数据文件中；(3) 能够读取数据文件中图的信息，创建图；(4) 能够显示最小生成树，包括起始和终点的序号以及最小生成树的代价。图1 给定的图2. 总体设计对于一个无相连通图G=(V,E)，设G是它的一个子图，如果G满足下列条件：(1) G中包含了G中所有顶点，即V(G)=V(G)；(2) G是连通图；(3) G中无回路。则称G 是G的一棵生成树。如果无相连通图是一个网，那么它的所有生成树中必有一棵边的权值总和最小的生成树，则称这棵生成树是最小代价生成树，简称为最小生成树。最小生成树的概念可以应用到许多实际问题，例如：计算城市之间道路构造问题，要想使总的造价最低，实际上就是寻找该网络的最小生成树。根据任务与需求，该程序需要能够输入数据、保存文件、读取文件、创建图、显示最小生成树。最小生成树的常用算法有两种，分别使用这两种方法进行最小生成树的计算。系统功能模块如图：图2 系统功能模块图3. 详细设计3.1 最小生成树算法常见的两种构造最小生成树的算法是Prim算法和Kruskal算法。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 (u,v)=minwuv|uU，vV-UT=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中，同时把两个连通分量连接为一个分量；若被考察边的两个顶点属于一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。3.2 详细设计在Prim算法中，关键在于集合T的表示，可以设置uSet数组，数组长度为顶点个数，uSeti的值为1时，表示顶点i加入集合T中，uSeti的值为0时，表示顶点i未加入集合T中，设定一个循环来进行最小生成树的计算，循环开始前将顶点0加入到集合T中，循环结束条件为所有的顶点都已在集合T中。循环体的内容是：遍历所有的边找出权值最小的边，且该条边的两个顶点m和n满足m在集合T中，n不在集合T中，则该边为最小生成树中的一条边，同时将顶点n加入到集合T中。在Kruskal算法中，同样引入一个uSet数组，数组长度为顶点数目，uSetn值为m时，说明顶点n在顶点集合m中，最初每个顶点各自为一个连通分量，并分别赋予一个编号，共有顶点数目个连通分量。设定一个循环来进行最小生成树的计算，循环开始前将顶点0加入到集合T中，循环终止条件为所有的顶点均进行了归并，也就是所有顶点都处在同一个连通分量当中。循环体的内容是：遍历所有的边找出权值最小的边，且该条边的两个顶点m和n两个连通分量合并。在实现连通分量合并时，可将m和n的uSet值进行比较，取其小者，并将该值赋予和m或n的uSet值相同的所有顶点，即完成了m和n两个连通分量的合并