课程设计-最小生成树.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)=min{wuv|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中，同时把两个连通分量连接为一个分量；若被考察边的两个顶点属于一个连通分量，则舍去此边，以免造成回路，如此下去，当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加入到集合T中。 在Kruskal算法中，同样引入一个uSet数组，数组长度为顶点数目，uSet[n]值为m时，说明顶点n在顶点集合m中，最初每个顶点各自为一个连通分量，并分别赋予一个编号，共有顶点数目个连通分量。设定一个循环来进行最小生成树的计算，循环开始前将顶点0加入到集合T中，循环终止条件为所有的顶点均进行了归并，也就是所有顶点都处在同一个连通分量当中。循环体的内容是：遍历所有的边找出权值最小的边，且该条边的两个顶点m和n两个连通分量合并。在实现连通分量合并时，可将m和n的uSet值进行比较，取其小者，并将该值赋予和m或n的uSet值相同的所有顶点，即完成了m和n两个连通分量的合并。 4. 编码 5.测试 图3 系统界面 图4 第一条路径信息输入 图5 把路径信息写入内存 图6