构造可以使N个城市连接的最小生成树.doc.doc

构造可以使 N 个城市连接的最小生成树一、设计目的(一)目的给定一个地区的 n 个城市间的距离网,用 Prim 算法或 Kruskal 算法建立最小生成树,并计算得到的最小生成树的代价。(二)程序所能达到的功能 1 .城市间的道路网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义, 若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。 2. 显示出城市间道路网的邻接矩阵。 3. 最小生成树中包括的边及其权值,并显示得到的最小生成树的总代价。(三) 程序执行命令输入城市数、道路数→输入城市名→输入道路信息→执行 Kruskal 算法→执行 Prim 算法→输出最小生成树。二、设计内容(一)算法设计与分析(1) 问题描述: 假设要在 n 个城市之间建立通信联络网, 则连通 n 个城市只需要 n-1 条路线。这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网。在每两个城市之间都可以设置一条线路, 相应地都要付出一定的经济代价。n 个城市之间, 最多可能设置 n( n-1 ) /2 条线路,那么,如何在这些可能的线路中选择 n-1 条,以使总的耗费最少呢? 可以用连通网来表示 n 个城市以及 n 个城市间可能设置的通信线路,其中网的顶点表示城市, 边表示两个城市之间的线路, 赋予边的权值表示相应的代价。对于 n 个顶点的连通网可以建立许多不同的生成树, 每一棵生成树都可以是一个通信网。现在选择使总的费用最少的生成树。一棵生成树的代价就是书上各边的代价之和。(2 )关于带权网络的存储形式要实现对于任意给定带权网络和顶点, 运用 PRIM 基本算法思想求解所有的最小生成树的运算。在这里我们首先要明确所选用的数据结构, 即选用何种数据结构存储来存储带权网络, 这是必选首先解决的问题, 所以我们选择了图的邻接矩阵存储方式来存储带权网络, 建图时采用邻接矩阵的结构, 定义邻接矩阵用到了一维数组和二维数组, 分别存储顶点信息和边的权值。由于该算法对图中的边的权值频繁比较, 所以采用邻接矩阵比较方便, 并在此基础上实现带权网络的建立以及输出显示。(3)P rim 算法的基本思想: 此算法是普利姆与 1957 年提出的一种构造最小生成树的算法,主要思想是:假设 N= (V, {E} )是连通网, TE 是N 上最小生成树中边的集合。算法从 U={u 0 }(u 0∈ V),TE={} 开始,重复执行下述操作:在所有 u∈ U,v ∈ V-U 的边( u,v )∈E 中找一条代价最小的边( u 0 ,v 0 )并入集合 TE ,同时 v 0 并入 U ,直至 U=V 为止。此时 TE 中必有 n-1 条边,则 T= (V, {E} ) 为N 的最小生成树。对于最小生成树问题最小生成树是指在所有生成树中, 边上权值之和最小的生成树, 另外最小生成树也可能是多个,他们之间的权值之和相等(4 )概要设计: 通过邻接矩阵的建立,可以将任意两点的权值存入其中,便于进行各边的权值的比较修改, 在普利姆算法中,为实现这个算法需附设一个辅助数组 closedge ,以记录从 U到 V-U 具有最小代价的边,对每个顶点 vi∈ V-U, 在辅助数组中存在一个相应分量 closedge[i-1] ,他包括两个域,其中 lowcost 存储该边上的权值。显然, closedge[i-1].lowcost=Min{cost(u,vi)| u∈ U} 从算法可以看出每加入一个顶点到 U 中, closedge 数组都会发生相应的变化。程序模块之间的调用: 在主函数中调用邻接矩阵的初始化函数, 邻接矩阵的生成函数, PRI M 算法的函数, 图的构造函数, 输出函数。邻接矩阵的生成函数主要解决的是边的信息存储问题,而 PRIM 算法的函数是解决计算出最小生成树的功能。(5 )抽象数据类型结构体数组的定义: #ifndef ADJACENCYMATRIXED // 防止该头文件被重复引用#define ADJACENCYMATRIXED // 而引起的数据重复定义#define INFINITY 32767 // 最大值∞#define MAX_VERTEX_NUM 20 // 最大顶点个数 typedef int VRType; // 权值,即边的值 typedef char InfoType; // 附加信息的类型,后面使用时会定义成一个指针 typedef char VertexType[MAX_VERTEX_NUM]; // 顶点类型 typedef enum {DG=1, DN, UDG, UDN} GraphKind; //{ 有向图,有向网,无向图,无向网} typedef struct ell { VRType adj;