建立n个城市间的最小生成树

《建立n个城市间的最小生成树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录设计要求-1-问题重述-1-基本要求-2-概要设计-2-2.1主界面的设计-2-2.2存储结构的设计本系统-3-2.2.1顺序表的基本概念-3-2.2.2图的邻接矩阵的基本概念-4-2.2.3最小生成树的基本概念-5-模块设计-6-3.1n个城市连接的最小生成树-6-3.2模块作用用途中的顶点表示-6-3.3模块及模块调用关系-6-3.2.1“SeqList.h”顺序存储结构存放结点信息-7-3.2.2“AdjMGraph.h”邻接矩阵存储结构存放边的信息-7-3.2.3最小生成树的生成过程-8-3.3

2、系统子程序及功能设计-9-3.3.1定义数组-9-3.3.2定义集合-10-3.3.3定义lowcost-10-3.3.4修改权值-10-3.3.5带权图-10-3.4算法描述-12-3.4.1流程图-12-测试结果及分析-14-测试结果-14-4.2结果分析-17-4.3错误分析-17-源程序-17-1设计要求1.1问题重述选择6-10个城市模拟在城市之间建立通信网络，只需要架设通信路线就可以，以最低的经济花费建设通信网，即用Prim算法或Kreskas算法生成一个网的最小生成树，并计算得到的最小生成树的

3、代价。-25-1.2基本要求u城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本上的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括那些城市间的道路，并显示得到的最小生成树的代价。u表示城市间距离网的邻接矩阵u最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。2概要设计为了实现以上功能，可以从以下主界面构造、存储结构采用、系统功能设置等三个方面进行分析设计。将图的结点信息存放在一个顺序表中，图的边信息存储在一个二维数组edg

4、e[MaxVertices][MaxVertices]中，这样就实现了用邻接矩阵存放城市间的距离网。在Prim算法的函数用两个参数，一个是图G为邻接矩阵存储结构的图；另一个是通过函数得到的最小生成树的结点数据和相应结点的边的权值数据closeVertex.2.1主界面的设计为了首先需要设计一个主界面子程序，以链接系统的各项子功能运行界面如图1所示-25-图12.2存储结构的设计本系统采用图结构类型，存储抽象n个城市模拟在城市之间建立通信网络，其中各城市用邻接矩阵类型存储。2.2.1顺序表的基本概念当采用C语

5、言描述数据结构时问题时，实现顺序存储结构的方法是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元内，这样，线性表中逻辑上相邻的数据元素在物理存储地址上也相邻，数据元素间的逻辑上的前驱，后继逻辑关系就表现在数据元素的存储单元的物理前后位置关系上。-25-数组有静态数组和动态数组两种。静态数组存储空间的申请和释放有系统自动完成，动态数组存储空间的申请和释放由用户调用系统函数完成。无论是静态数组还是动态数组，其功能都是向系统申请一块地址连续的有限空间，只是申请的方法不同，顺序表一般采用静态数组方法

6、实现数据元素的存储。顺序表定义结构体如下：Typedefstruct{DataTypelist[Maxsize];Intsize;}SeqList;其中，DataType为数组（即数据元素）的数据类型，Maxsize表示数组的最大元素个数，list表示顺序表的数组名，size表示顺序表中当前存储的数据元素个数，它必须满足size<=Maxsize，SeqList是该结构体的名称。2.2.2图的邻接矩阵的基本概念由图的定义可知，图的信息包括两部分，图中结点的信息和描述之间关系的边的信息。结点信息的描述问题，是

7、一个简单的表存储结构问题。对于一个有n个节点的图，由于每个结点都可能与其他n-1个结点成为邻接结点，所以边之间关系的描述问题，实际上是一个n*n矩阵的计算机存储表示问题。在图的邻接矩阵存储结构中，节点信息使用一维数组存储，边的邻接矩阵使用二维数组存储，无向图的邻接矩阵一定是对称矩阵。当图中结点数目较小且边较多时，采用图的邻接矩阵存储结构效率较高；当图中结点数目较大且边的数目远小于相同结点的完全图的边数时，采用图的邻接表存储结构效率较高。图的结构体定义如下：typedefstruct{SeqListVerti

8、ces;intedge[MaxVertices][MaxVertices];-25-intnumOfEdges;}AdjMGraph;2.2.3最小生成树的基本概念一个有n个结点的连通图的生成树是原图的极小连通子图，他包含原图中的所有n个结点，并且保持图连通的最少的边。由生成树的定义可知：（1）若再生成树中删除一条边就会使该生成树因变成非连通图而不再满足生成树的定义；（2）若在生成树中增加一条边就会使生成树中存在