建立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.1 n个城市连接的最小生成树- 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算法生成一个网的最小生成树，并计算得到的最小生成树的代价。 1.

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

4、rim算法的函数用两个参数，一个是图G为邻接矩阵存储结构的图；另一个是通过函数得到的最小生成树的结点数据和相应结点的边的权值数据closeVertex.2.1 主界面的设计为了 首先需要设计一个主界面子程序，以链接系统的各项子功能运行界面如图1所示 图12.2 存储结构的设计本系统采用图结构类型，存储抽象n个城市模拟在城市之间建立通信网络，其中各城市用邻接矩阵类型存储。2.2.1 顺序表的基本概念 当采用C语言描述数据结构时问题时，实现顺序存储结构的方法是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元内，这样，线性表中逻辑上相邻的数据元素在物理存储地址上也相邻，数据元素间的逻

5、辑上的前驱，后继逻辑关系就表现在数据元素的存储单元的物理前后位置关系上。 数组有静态数组和动态数组两种。静态数组存储空间的申请和释放有系统自动完成，动态数组存储空间的申请和释放由用户调用系统函数完成。无论是静态数组还是动态数组，其功能都是向系统申请一块地址连续的有限空间，只是申请的方法不同，顺序表一般采用静态数组方法实现数据元素的存储。 顺序表定义结构体如下： Typedef struct DataType listMaxsize; Int size;SeqList;其中，DataType为数组（即数据元素）的数据类型，Maxsize表示数组的最大元素个数，list表示顺序表的数组名，size

6、表示顺序表中当前存储的数据元素个数，它必须满足size<= Maxsize，SeqList是该结构体的名称。2.2.2 图的邻接矩阵的基本概念由图的定义可知，图的信息包括两部分，图中结点的信息和描述之间关系的边的信息。结点信息的描述问题，是一个简单的表存储结构问题。对于一个有n个节点的图，由于每个结点都可能与其他n-1个结点成为邻接结点，所以边之间关系的描述问题，实际上是一个n*n矩阵的计算机存储表示问题。在图的邻接矩阵存储结构中，节点信息使用一维数组存储，边的邻接矩阵使用二维数组存储，无向图的邻接矩阵一定是对称矩阵。当图中结点数目较小且边较多时，采用图的邻接矩阵存储结构效率较高；当图中

7、结点数目较大且边的数目远小于相同结点的完全图的边数时，采用图的邻接表存储结构效率较高。图的结构体定义如下：typedef struct SeqList Vertices; int edgeMaxVertices MaxVertices; int numOfEdges;AdjMGraph;2.2.3 最小生成树的基本概念 一个有n个结点的连通图的生成树是原图的极小连通子图，他包含原图中的所有n个结点，并且保持图连通的最少的边。 由生成树的定义可知：（1）若再生成树中删除一条边就会使该生成树因变成非连通图而不再满足生成树的定义；（2）若在生成树中增加一条边就会使生成树中存在回路而不再满足生成树的定

8、义；（3）一个连通图的生成树可能得到不同的生成树。使用不同的寻找方法可以得到不同的生成树。另外，从不同的初始结点出发也可以得到不同的生成树。 从生成树的定义显然可以证明，对于有n个结点的无向连通图，无论他的生成树的形状如何，一定有且只有n-1条边。 如果无向连通图是一条带权图，那么他的所有生成树中必有一颗边的权值总和为最小的生成树，称这棵生成树为最小代价生成树，简称最小生成树。 从最小生成树的定义可知，构造有n个结点的无向连通带权图的最小生成树必须满足以下三点：（1）构造的最小生成树必须包括n个结点（2）构造的最小生成树中有且只有n-1条边（3）构造的最小生成树中不存在回路假设G=(V,E)为

9、一个带权图，其中V为带权图中结点的集合，E为带权图中的边的权值集合。设置两个信新的集合U和T，其中U用于存放带权图G的最小生成树的结点的集合，T用于存放带权图G的最小生成树边的权值的集合。普利姆算法思想是：令集合U的初值为Uu0（即假设构造最小生成树时从结点u0开始），集合T 的初值为T=。从所有结点u属于U和结点v属于V但不属于U的带权边中选出具有最小权值的边（u，v），将结点v加入集合U中，将边（u，v）加入集合T中。如此不断重复，当U=V时，最小生成树便构造完毕。此时集合U中存在着最小生成树的结点，集合T中存放着最小生成树边的权值集合。3 模块设计3.1 n个城市连接的最小生成树选择6-

10、10个城市模拟在城市之间建立通信网络，只需要架设通信路线就可以，以最低的经济花费建设通信网，即生成一个网的最小生成树，各城市分别用字母AG表示。3.2 模块作用用途中的顶点表示头文件用来存放邻接矩阵存储结构定义以及相应的图的操作函数与图的创建及普里姆函数的设计。主函数“prim.cpp”来测试程序。3.3 模块及模块调用关系3.2.1 “SeqList.h”顺序存储结构存放结点信息a.初始化ListInitiate(L)：初始化线性表L。b.求当前数据元素个数ListLength（L）：函数返回线性表L的当前数据元素的个数c.插入数据元素ListInsert(L,i,x)：在现象表L的第i个数

11、据前插入数据元素x，如果插入成功返回1，插入失败返回0。其约束条件为0iListLength（L），即若i=0，表示在第一个元素之前插入数据元素x，若i= ListLength（L）-1，表示在最后一个元素前插入数据元素x，若i= ListLength（L），表示在最后一个元素之后插入数据元素x。d.删除数据元素ListDelete(L,i,x)：删除线性表L的第i个元素，所删除的数据元素由输出参数x带回。如果删除成功返回1，删除失败返回0，其约束条件为0iListLength（L）-1，若i=0，表示删除第一个数据元素，若i= ListLength（L）-1，表示删除最后一个数据元素。e.取

12、数据元素ListGet(L,i,x)：取线性表L的第i个数据元素，所取得数据元素由输出参数x带回，取元素成功返回1，取元素失败返回0。其约束条件为 0iListLength（L）-1，若i=0，表示取第一个数据元素，若i= ListLength（L）-1，表示取最后一个数据元素。3.2.2“AdjMGraph.h”邻接矩阵存储结构存放边的信息a. 初始化图G，n为结点个数。 Initiate(AdjMGraph *G, int n)b. 在图G中插入结点vertex InsertVertex(AdjMGraph *G, DataType vertex)c. 在图G中插入边<v1,v2&g

13、t;，边<v1,v2>的权值为weightInsertEdge(AdjMGraph *G, int v1,int v2,int weight)d. 在图G中删除边<v1,v2>DeleteEdge(AdjMGraph *G,int v1,int v2)e. 删除图G中的结点v以及与该节点相关的所有边DeleteVerten(AdjMGraph *G,int v)f. 在图G中寻找序号为v的结点的第一个邻接结点GetFirstVex(AdjMGraph G,int v)g.在图G中寻找v1结点的邻接结点v2的下一个邻接结点.GetNextVex(AdjMGraph G,i

14、nt v1,int v2)3.2.3 最小生成树的生成过程 下图中给出了用普利姆算法构造最小生成树的过程。(a)为一个有7个结点10条边的无向边的带权图。初始集合U=A，集合VU=B，C，D，E，F，G，T=，如图（b）所示，此时，存在两条一个结点在U、另一个结点在集合VU中的边，具有最小权值的边（A，B），权值为50，把结点B从VU加入到集合U中，把边（A，B）加入到T中，如图（c）所示，在所有以u为集合U中结点、v为集合VU中结点的边（u，v）中寻找具有最小权值的边（u，v），寻找到的是（B,E），权值为40，把结点E从集合VU中加入到集合U中，把边（B,E）加入到T中，如图（d）所示，随

15、后依次从集合VU加入到集合U中的结点为D，F，G，C，依次加入到T中的边为（E，D），权值为50，（D,F）权值为30，（D,G），权值为42，（G，C），权值为45，分别如图（e）（f）（g）（h）所示，最后得到的图（h）就是从A结点出发构造的最小生成树。 (a) (b) (c) (d) (e) (f) (g) (h)3.3 系统子程序及功能设计3.3.1 定义数组函数中定义一个临时数组lowcost，数组元素lowcostv中保存了集合中结点ui与集合VU中结点uj的所有边中当前具有最小权值的边（u，v）。 3.3.2 定义集合集合U的初值为U=序号为j的结点。Lowcost的初始值为邻接

16、矩阵数组中第j行的值，这样初始时lowcost中就存放了从集合U中的结点j到VU中各节点的权值。3.3.3 定义lowcost每次从lowcost中寻找具有最小权值的边，根据lowcost的定义，这样的边其弧头结点必然为集合U中的结点，其弧尾结点必然为集合VU中的结点，当选到这样的边（u，v）时，就保存其结点数据和权值数据到参数closevertex中，并将lowcostv置为-1，表示点v加入到了集合U中。3.3.4 修改权值当节点v从集合VU加入到集合U后，若存在一条边（u，v），u是集合U的结点，v是集合VU的节点，且边（u，v）较原先lowcostv的权值更小，则用这样的权值修改原先l

17、owcostv中相应权值。3.3.5 带权图以图（a）所示的带权图为例，调用普利姆函数时数组lowcost的动态变化过程如下所示。其中第一图表示初始结点0在集合U中，结点0到其他结点有两条边，权值分别为50和60。第二图表示结点1加入到集合U中，结点1加入集合U后，因结点1到结点3存在一条权值为65的边，该权值小于原先的无穷大，所以需要把，lowcost3改为65，因结点1到结点4存在一条权值为40的边，该权值小于原先的无穷大，所以需要把lowcost4改为40，第三图表示结点4加入到集合U后的状态，第四图表示结点3加入集合u后的状态，第五图表示结点5加入到集合U后的状态，第六图表示结点6加入

18、到集合U后的状态，最后一图表示结点3加入到集合U后的状态。 lowcost lowcost lowcost lowcost lowcost lowcost lowcost 3.4 算法描述3.4.1 流程图创建用邻接矩阵表示的城市道路网输入城市属N=7道路数e=20输入城市a输入表示两个城市间距离RowColWeight rcw返回 图2 创建邻接矩阵流程图判断程序是否为真Prim算法用铺助数组lowCost输入初始城市序号jfor(i=1;i<n;i+) 初始化lowCosti=G.edgeji从结点O出发构造最小生成树结点寻找当前最小权值的边所对应的弧头minCost=MaxWeig

19、ht输出找到的道路标记城市输出总代价判断是否继续：1-继续；2-退出1：返回程序开始处2：退出结束 Prim算法流程图4 测试结果及分析4.1测试结果4.2 结果分析当从一个第一个顶点开始以此作为生成树的初始状态，然后找出与其之间权值最小的顶点2并把顶点2添加到该生成树中，以此类推找出与顶点2之间权值最小的顶点。再把找出的顶点添加到生成树中直到最后一个顶点添加到生成树上是得到所求的生成数即为最小生成树。4.3 错误分析在本次课程设计的过程中，出现诸多错误，比如分号没有打以及一些错打和少打的情况，在此不做一一的介绍，只介绍一些较大的错误。1、本应从任一节点接入均可以构造最小生成树，所以在运行普利

20、姆算法时需要在创建数组之前输入一个城市的结点序号，在开始时，只是将数组中的j写入，并没有赋初始值，所以在程序运行时出现了错误。2、在成功运行从任意结点构造生成树后，由于需要关闭运行框后才能进行下一次的构造，这是在实际运行中是不允许的，所以要求在程序开始时加一个判断语句，只要在执行完后进行是否继续的判断就可以直接再次运行普利姆算法而不需要关闭运行框后再重新运行程序。5 源程序头文件：AdjMGraph.htypedef int DataType;typedef struct DataType listMaxSize;int size;SeqList;void ListInitiate(SeqLi

21、st *L)L->size=0;int ListLength(SeqList L)return L.size;int ListInsert(SeqList *L,int i,DataType x)int j;if(L->size>=MaxSize)printf("顺序表已满无法插入！n");return 0;else if(i<0|i>L->size)printf("参数i不合法！n");return 0;else for(j=L->size;j>i;j-) L->listj=L->listj-

22、1; L->listi=x; L->size+; return 1;int ListDelete(SeqList *L,int i,DataType*x)int j;if(L->size<=0)printf("顺序表已空无数据可删！n");return 0;else if(i<0|i>L->size-1)printf("参数i不合法！n");return 0;else*x=L->listi;for(j=i;j<L->size;j+) L->listj=L->listj+1; L-&g

23、t;size-; return 1; int ListGet(SeqList L,int i,char*x) if(i<0|i>L.size-1)printf("参数i不合法！n");return 0; else *x=L.listi; return 1; typedef structSeqList Vertices; /* 存放结点的顺序表 */int edgeMaxVerticesMaxVertices; /* 存放边的邻结矩阵地 */int numOfEdges; /* 边的条数 */AdjMGraph; /* 图的结构体定义 */void Initiat

24、e(AdjMGraph *G, int n) /* 初始化 */int i,j;for(i=0;i<n;i+)for(j=0;j<n;j+)if(i=j) G->edgeij=0;else G->edgeij=MaxWeight;G->numOfEdges=0; /* 边的条数置为0 */ListInitiate(&G->Vertices); /*顺序表初始化 */void InsertVertex(AdjMGraph *G, DataType vertex) /* v在图G中插入结点vertex */ListInsert(&G->Ve

25、rtices, G->Vertices.size,vertex); /* 顺序表尾插入 */void InsertEdge(AdjMGraph *G, int v1,int v2,int weight) /*在图G中插入边<v1,v2>，边<v1,v2>的权为weight */if(v1<0 | v1>G->Vertices.size | v2>G->Vertices.size|v2<0)printf("参数v1或v2越界出错! n");exit(1);G->edgev1v2=weight;G->

26、numOfEdges+;void DeleteEdge(AdjMGraph *G,int v1,int v2)/*在图G中删除边<v1,v2> */if(v1<0 | v1>G->Vertices.size | v2<0 | v2>G->Vertices.size | v1=v2)printf("掺数v1或v2越界出错! n");exit(1);if(G->edgev1v2=MaxWeight | v1=v2)printf("该边不存在!n");exit(0);G->edgev1v2=MaxWe

27、ight;G->numOfEdges-;void DeleteVertex(AdjMGraph *G,int v) /*删除结点V*/int n=ListLength(G->Vertices),i,j;DataType x;for(i=0;i<n;i+) /*计算删除后的边数*/for(j=0;j<n;j+)if(i=v|j=v) && G->edgeij>0 && G->edgeij<MaxWeight)G->numOfEdges-; /*计算被删除边*/for(i=v;i<n;i+) /*删除第v行

28、*/for(j=0;j<n;j+)G->edgeij=G->edgei+1j;for(i=0;i<n;i+) /*删除第v列*/for(j=v;j<n;j+)G->edgeij=G->edgeij+1;ListDelete(&G->Vertices,v,&x);int GetFirstVex(AdjMGraph G,int v)/*在图G中寻找序号为v的结点的第一个邻接结点*/*如果这样的邻接结点存在，返回该邻接结点的序号；否则，返回-1*/int col;if(v<0 | v>G.Vertices.size)prin

29、tf("参数v1越界出错!n");exit(1);for(col=0;col<G.Vertices.size;col+)if(G.edgevcol>0 && G.edgevcol<MaxWeight) return col;return -1;int GetNextVex(AdjMGraph G,int v1,int v2)/*在图G中寻找v1结点的邻接结点v2的下一个邻接结点*/*如果这样的邻接结点存在，返回该邻接结点的序号；否则，返回-1*/*v1和v2都是相应结点的序号*/ int col; if(v1<0 | v1>G.

30、Vertices.size | v2<0 | v2>G.Vertices.size) printf("参数v1或v2越界出错!n"); exit(1); for(col=v2+1;col<G.Vertices.size;col+) if(G.edgev1col>0 && G.edgev1col<MaxWeight) return col; return -1;typedef structint row; /*行下标*/int col; /*列下标*/int weight; /*权值*/RowColWeight; /*边信息结构体

31、定义*/void CreatGraph(AdjMGraph *G,char V,int n,RowColWeight E,int e)/*在图G中插入v个结点信息V和e条边信息E*/int i,k;Initiate(G,n); /*结点顺序表初始化*/for(i=0;i<n;i+)InsertVertex(G,Vi); /*结点插入*/for(k=0;k<e;k+)InsertEdge(G,Ek.row,Ek.col,Ek.weight); /*边插入*/typedef structVerT vertex;int weight;MinSpanTree;void Prim(AdjMG

32、raph G, MinSpanTree closeVertex)/*用普里姆算法建立带权图G的最小生成树closeVertex*/VerT x;int n=G.Vertices.size,minCost;int *lowCost=(int *)malloc(sizeof(int)*n);int i,j,k; printf("请输入第一个城市:"); scanf("%d",&j);for(i=0;i<n;i+) /*初始化*/ lowCosti=G.edgeji; /*从结点j出发构造最小生成树*/ ListGet(G.Vertices,j,

33、&x); /*取结点j*/ closeVertexj.vertex=x; /*保存结点j*/ lowCostj=-1; /*标记结点j*/ for(i=1;i<n;i+)/*结点寻找当前最小权值的边所对应的弧头K*/minCost=MaxWeight;for(j=0;j<n;j+) if(lowCostj<minCost && lowCostj>0) minCost=lowCostj; k=j;ListGet(G.Vertices,k,&x); /*取弧头结点K*/closeVertexi.vertex=x; /*保存弧头结点K*/clo

34、seVertexi.weight=minCost; /*保存相应的权值*/lowCostk=-1; /*标记结点K*/*根据加入集合U的结点K修改lowCost中的数值*/for(j=0;j<n;j+)if(G.edgekj<lowCostj)lowCostj=G.edgekj;主文件：prim.cpp#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedef char VerT;#define MaxSize 100 #define MaxVertices 10#define MaxWeight 10000#define N 7#include"AdjMGraph.h"void main(void)while(1)AdjMGraph g;char a='A','B','C','D','E','F','G'RowColWeight rcw=0