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

目录设计要求........................................................-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系统子程序及功能设计........................................-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结果分析..................................................-16-4.3错误分析..................................................-16-源程序.........................................................-17-1 设计要求1.1 问题重述选择6-10个城市模拟在城市之间建立通信网络，只需要架设通信路线就可精品文档放心下载以，以最低的经济花费建设通信网，即用Prim算法或Kreskas算法生成一个网感谢阅读的最小生成树，并计算得到的最小生成树的代价。-/1.2 基本要求城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本上的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括那些城市间的道路，并显示得到的最小生成树的代价。谢谢阅读表示城市间距离网的邻接矩阵最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。谢谢阅读2 概要设计为了实现以上功能，可以从以下主界面构造、存储结构采用、系统功能设置谢谢阅读等三个方面进行分析设计。将图的结点信息存放在一个顺序表中，图的边信息存感谢阅读储在一个二维数组edge[MaxVertices][MaxVertices]中，这样就实现了用邻接精品文档放心下载矩阵存放城市间的距离网。在Prim算法的函数用两个参数，一个是图G为邻接精品文档放心下载矩阵存储结构的图；另一个是通过函数得到的最小生成树的结点数据和相应结点感谢阅读的边的权值数据closeVertex.2.1 主界面的设计为了 首先需要设计一个主界面子程序，以链接系统的各项子功能运行界面如图1所示-/图12.2 存储结构的设计本系统采用图结构类型，存储抽象n个城市模拟在城市之间建立通信网络，其中各城市用邻接矩阵类型存储。感谢阅读2.2.1 顺序表的基本概念当采用C语言描述数据结构时问题时，实现顺序存储结构的方法是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元内，这样，线性表中逻辑上相邻的数据元素在物理存储地址上也相邻，数据元素间的逻辑上的前驱，后继逻辑关系就表现在数据元素的存储单元的物理前后位置关系上。精品文档放心下载数组有静态数组和动态数组两种。静态数组存储空间的申请和释放有系统自感谢阅读-/动完成，动态数组存储空间的申请和释放由用户调用系统函数完成。无论是静态数组还是动态数组，其功能都是向系统申请一块地址连续的有限空间，只是申请的方法不同，顺序表一般采用静态数组方法实现数据元素的存储。精品文档放心下载顺序表定义结构体如下：Typedefstruct{DataTypelist[Maxsize];Intsize;}SeqList;其中，DataType为数组（即数据元素）的数据类型，Maxsize表示数组的最精品文档放心下载大元素个数，list表示顺序表的数组名，size表示顺序表中当前存储的数据元素精品文档放心下载个数，它必须满足size<=Maxsize，SeqList是该结构体的名称。谢谢阅读2.2.2 图的邻接矩阵的基本概念由图的定义可知，图的信息包括两部分，图中结点的信息和描述之间关系的边的信息。结点信息的描述问题，是一个简单的表存储结构问题。对于一个有n个节点的图，由于每个结点都可能与其他n-1个结点成为邻接结点，所以边之间关系的描述问题，实际上是一个n*n矩阵的计算机存储表示问题。谢谢阅读在图的邻接矩阵存储结构中，节点信息使用一维数组存储，边的邻接矩阵使用二维数组存储，无向图的邻接矩阵一定是对称矩阵。谢谢阅读当图中结点数目较小且边较多时，采用图的邻接矩阵存储结构效率较高；当图中结点数目较大且边的数目远小于相同结点的完全图的边数时，采用图的邻接表存储结构效率较高。精品文档放心下载图的结构体定义如下：typedefstruct{SeqListVertices;intedge[MaxVertices][MaxVertices];感谢阅读-/intnumOfEdges;}AdjMGraph;2.2.3 最小生成树的基本概念一个有n个结点的连通图的生成树是原图的极小连通子图，他包含原图中的所有n个结点，并且保持图连通的最少的边。感谢阅读由生成树的定义可知：（1）若再生成树中删除一条边就会使该生成树因变成非连通图而不再满足生成树的定义；（2）若在生成树中增加一条边就会使生成树中存在回路而不再满足生成树的定义；（3）一个连通图的生成树可能得到不同的生成树。使用不同的寻找方法可以得到不同的生成树。另外，从不同的初始结点出发也可以得到不同的生成树。谢谢阅读从生成树的定义显然可以证明，对于有n个结点的无向连通图，无论他的生成树的形状如何，一定有且只有n-1条边。精品文档放心下载如果无向连通图是一条带权图，那么他的所有生成树中必有一颗边的权值总和为最小的生成树，称这棵生成树为最小代价生成树，简称最小生成树。感谢阅读从最小生成树的定义可知，构造有n个结点的无向连通带权图的最小生成树必须满足以下三点：精品文档放心下载（1）构造的最小生成树必须包括n个结点（2）构造的最小生成树中有且只有n-1条边（3）构造的最小生成树中不存在回路假设G=(V,E)为一个带权图，其中V为带权图中结点的集合，E为带权图中的边的权值集合。设置两个信新的集合U和T，其中U用于存放带权图G的最小生成树的结点的集合，T用于存放带权图G的最小生成树边的权值的集合。精品文档放心下载普利姆算法思想是：令集合U的初值为U{u0}（即假设构造最小生成树时从结点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个城市模拟在城市之间建立通信网络，只需要架设通信路线就可谢谢阅读以，以最低的经济花费建设通信网，即生成一个网的最小生成树，各城市分别用谢谢阅读字母A—G表示。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个数据前插入数据元素x，如果插入成功返回1，插入失败返回0。其约束条件为0≤i≤ListLength（L），即谢谢阅读i=0，表示在第一个元素之前插入数据元素x，若i=ListLength（L）-1，表示在最后一个元素前插入数据元素x，若i=ListLength（L），表示在最后一个元素之后插入数据元素x。谢谢阅读d.删除数据元素ListDelete(L,i,x)：删除线性表L的第i个元素，所删除的数据元素由输出参数x带回。如果删除成功返回1，删除失败返回0，其约束条件感谢阅读0≤i≤ListLength（L）-1，若i=0，表示删除第一个数据元素，若i=ListLength谢谢阅读（L）-1，表示删除最后一个数据元素。e.取数据元素ListGet(L,i,x)：取线性表L的第i个数据元素，所取得数据元谢谢阅读素由输出参数x带回，取元素成功返回1，取元素失败返回0。其约束条件为谢谢阅读0≤i≤ListLength（L）-1，若i=0，表示取第一个数据元素，若i=ListLength（L）谢谢阅读-1，表示取最后一个数据元素。3.2.2“AdjMGraph.h”邻接矩阵存储结构存放边的信息精品文档放心下载初始化图G，n为结点个数。Initiate(AdjMGraph*G,intn)感谢阅读在图G中插入结点vertexInsertVertex(AdjMGraph*G,DataTypevertex)感谢阅读-/在图G中插入边<v1,v2>，边<v1,v2>的权值为weightInsertEdge(AdjMGraph*G,intv1,intv2,intweight)谢谢阅读在图G中删除边<v1,v2>DeleteEdge(AdjMGraph*G,intv1,intv2)感谢阅读删除图G中的结点v以及与该节点相关的所有边DeleteVerten(AdjMGraph*G,intv)感谢阅读在图G中寻找序号为v的结点的第一个邻接结点GetFirstVex(AdjMGraphG,intv)感谢阅读g.在图G中寻找v1结点的邻接结点v2的下一个邻接结点.谢谢阅读GetNextVex(AdjMGraphG,intv1,intv2)精品文档放心下载3.2.3 最小生成树的生成过程下图中给出了用普利姆算法构造最小生成树的过程。(a)为一个有7个结点10条边的无向边的带权图。初始集合U={A}，集合V\U={B，C，D，E，F，G}，T={}，如图（b）所示，此时，存在两条一个结点在U、另一个结点在集合V\U中的边，具有最小权值的边（A，B），权值为50，把结点B从V\U加入到集合U中，把边（A，B）加入到T中，如图（c）所示，在所有以u为集合U中结点、v为集合V\U中结点的边（u，v）中寻找具有最小权值的边（u，v），寻找到的是（B,E），权值为40，把结点E从集合V\U中加入到集合U中，把边（B,E）加入到T中，如图（d）所示，随后依次从集合V\U加入到集合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，数组元素lowcost[v]中保存了集合中结点ui与集合V\U中结点uj的所有边中当前具有最小权值的边（u，v）。谢谢阅读-/3.3.2 定义集合集合U的初值为U={序号为j的结点}。Lowcost的初始值为邻接矩阵数组中第j行的值，这样初始时lowcost中就存放了从集合U中的结点j到V\U中各节点的权值。感谢阅读3.3.3 定义lowcost每次从lowcost中寻找具有最小权值的边，根据lowcost的定义，这样的边其弧头结点必然为集合U中的结点，其弧尾结点必然为集合V\U中的结点，当选到这样的边（u，v）时，就保存其结点数据和权值数据到参数closevertex中，并谢谢阅读lowcost[v]置为-1，表示点v加入到了集合U中。谢谢阅读3.3.4 修改权值当节点v从集合V\U加入到集合U后，若存在一条边（u，v），u是集合U的结点，v是集合V\U的节点，且边（u，v）较原先lowcost[v]的权值更小，则用这样的权值修改原先lowcost[v]中相应权值。感谢阅读3.3.5 带权图以图（a）所示的带权图为例，调用普利姆函数时数组lowcost的动态变化过程如下所示。其中第一图表示初始结点0在集合U中，结点0到其他结点有两条边，权值分别为50和60。谢谢阅读第二图表示结点1加入到集合U中，结点1加入集合U后，因结点1到结精品文档放心下载点3存在一条权值为65的边，该权值小于原先的无穷大，所以需要把，lowcost[3]精品文档放心下载-/改为65，因结点1到结点4存在一条权值为40的边，该权值小于原先的无穷大，精品文档放心下载所以需要把lowcost[4]改为40，第三图表示结点4加入到集合U后的状态，第四图表示结点3加入集合u后的状态，第五图表示结点5加入到集合U后的状态，第六图表示结点6加入到集合U后的状态，最后一图表示结点3加入到集合U后的状态。谢谢阅读lowcost lowcost lowcost lowcost lowcost精品文档放心下载lowcost lowcost-/3.4 算法描述3.4.1 流程图创建用邻接矩阵表示的城市道路网输入城市属N=7道路数e=20输入城市a[]输入表示两个城市间距离RowColWeightrcw[]返回图2 创建邻接矩阵流程图判断程序是否为真Prim算法用铺助数组lowCost[]输入初始城市序号j-/for(i=1;i<n;i++) 初始化lowCost[i]=G.edge[j][i]从结点O出发构造最小谢谢阅读生成树结点寻找当前最小权值的边所对应的弧头minCost=MaxWeight输出找到的道路标记城市输出总代价判断是否继续：1-继续；2-退出1：返回程序开始处2：退出结束Prim算法流程图-/测试结果及分析4.1测试结果-/-/4.2 结果分析当从一个第一个顶点开始以此作为生成树的初始状态，然后找出与其之间权感谢阅读值最小的顶点2并把顶点2添加到该生成树中，以此类推找出与顶点2之间权值精品文档放心下载最小的顶点。再把找出的顶点添加到生成树中直到最后一个顶点添加到生成树上谢谢阅读是得到所求的生成数即为最小生成树。4.3 错误分析在本次课程设计的过程中，出现诸多错误，比如分号没有打以及一些错打和感谢阅读少打的情况，在此不做一一的介绍，只介绍一些较大的错误。精品文档放心下载1、本应从任一节点接入均可以构造最小生成树，所以在运行普利姆算法时感谢阅读需要在创建数组之前输入一个城市的结点序号，在开始时，只是将数组中的j写精品文档放心下载入，并没有赋初始值，所以在程序运行时出现了错误。2、在成功运行从任意结点构造生成树后，由于需要关闭运行框后才能进行感谢阅读-/下一次的构造，这是在实际运行中是不允许的，所以要求在程序开始时加一个判感谢阅读断语句，只要在执行完后进行是否继续的判断就可以直接再次运行普利姆算法而谢谢阅读不需要关闭运行框后再重新运行程序。5 源程序头文件：AdjMGraph.htypedefintDataType;typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;voidListInitiate(SeqList*L)谢谢阅读{L->size=0;}intListLength(SeqListL){returnL.size;}intListInsert(SeqList *L,inti,DataTypex)感谢阅读{intj;if(L->size>=MaxSize){printf("顺序表已满无法插入！\n");return0;}elseif(i<0||i>L->size){printf("参数i不合法！\n");return0;}else-/{for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];L->list[i]=x;L->size++;return1;}}intListDelete(SeqList*L,inti,DataType*x)精品文档放心下载{intj;if(L->size<=0){printf("顺序表已空无数据可删！\n");return0;}elseif(i<0||i>L->size-1){printf("参数i不合法！\n");return0;}else{*x=L->list[i];for(j=i;j<L->size;j++)L->list[j]=L->list[j+1];L->size--;return1;}}intListGet(SeqListL,inti,char*x)感谢阅读{if(i<0||i>L.size-1){printf("参数i不合法！\n");return0;}else{*x=L.list[i];return1;}}typedefstruct{SeqListVertices;点的顺序表*/intedge[MaxVertices][MaxVertices];的邻结矩阵地*/感谢阅读intnumOfEdges;数*/}AdjMGraph;构体定义*/voidInitiate(AdjMGraph*G,intn)谢谢阅读*/{inti,j;for(i=0;i<n;i++)for(j=0;j<n;j++){if(i==j)G->edge[i][j]=0;elseG->edge[i][j]=MaxWeight;感谢阅读}G->numOfEdges=0;置为0*/ListInitiate(&G->Vertices);感谢阅读始化*/}voidInsertVertex(AdjMGraph*G,DataTypevertex)谢谢阅读中插入结点vertex*/{

-//* 存放结/* 存放边/* 边的条/*图的结/*初始化/*边的条数/*顺序表初/*v在图GListInsert(&G->Vertices,G->Vertices.size,vertex); /*顺序表尾精品文档放心下载插入*/}voidInsertEdge(AdjMGraph*G,intv1,intv2,intweight)精品文档放心下载/*在图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->edge[v1][v2]=weight;G->numOfEdges++;}voidDeleteEdge(AdjMGraph*G,intv1,intv2)谢谢阅读/*在图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->edge[v1][v2]==MaxWeight||v1==v2)谢谢阅读{printf("该边不存在!\n");exit(0);}G->edge[v1][v2]=MaxWeight;感谢阅读G->numOfEdges--;}voidDeleteVertex(AdjMGraph*G,intv)感谢阅读{

/*删除结点V*/intn=ListLength(G->Vertices),i,j;感谢阅读DataTypex;for(i=0;i<n;i++)

/*计算删除后的边数*/for(j=0;j<n;j++)if((i==v||j==v)

&&

G->edge[i][j]>0

&&G->edge[i][j]<MaxWeight)G->numOfEdges--;for(i=v;i<n;i++)

/*计算被删除边*//*删除第v行*/for(j=0;j<n;j++)G->edge[i][j]=G->edge[i+1][j];精品文档放心下载for(i=0;i<n;i++)/*删除第v列*/for(j=v;j<n;j++)G->edge[i][j]=G->edge[i][j+1];精品文档放心下载ListDelete(&G->Vertices,v,&x);精品文档放心下载}intGetFirstVex(AdjMGraphG,intv)精品文档放心下载/*在图G中寻找序号为v的结点的第一个邻接结点*/感谢阅读/*如果这样的邻接结点存在，返回该邻接结点的序号；否则，返回-1*/精品文档放心下载-/{intcol;if(v<0||v>G.Vertices.size)感谢阅读{printf("参数v1越界出错!\n");exit(1);}for(col=0;col<G.Vertices.size;col++)感谢阅读if(G.edge[v][col]>0&&G.edge[v][col]<MaxWeight)returncol;return-1;谢谢阅读}intGetNextVex(AdjMGraphG,intv1,intv2)精品文档放心下载/*在图G中寻找v1结点的邻接结点v2的下一个邻接结点*/感谢阅读/*如果这样的邻接结点存在，返回该邻接结点的序号；否则，返回-1*/谢谢阅读/*v1和v2都是相应结点的序号*/{intcol;if(v1<0||v1>G.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.edge[v1][col]>0&&G.edge[v1][col]<MaxWeight)returncol;return-1;感谢阅读}typedefstruct{introw;intcol;intweight;}RowColWeight;

/*行下标*//*列下标*//*权值*//*边信息结构体定义*/voidCreatGraph(AdjMGraph*G,charV[],intn,RowColWeightE[],inte)/*在图G中插入v个结点信息V和e条边信息E*/{感谢阅读inti,k;Initiate(G,n); /*结点顺序表初始化*/谢谢阅读for(i=0;i<n;i++)InsertVertex(G,V[i]); /*结点插入*/精品文档放心下载for(k=0;k<e;k++)InsertEdge(G,E[k].row,E[k].col,E[k].weight); /*边插入*/精品文档放心下载-/}typedefstruct{VerTvertex;intweight;}MinSpanTree;voidPrim(AdjMGraphG,MinSpanTreecloseVertex[])谢谢阅读/*用普里姆算法建立带权图G的最小生成树closeVertex[]*/精品文档放心下载{VerTx;intn=G.Vertices.size,minCost;精品文档放心下载int*lowCost=(int*)malloc(sizeof(int)*n);inti,j,k;感谢阅读printf("请输入第一个城市:");scanf("%d",&j);for(i=0;i<n;i++) /*初始化*/lowCost[i]=G.edge[j][i];/*从结点j出发构造最小生成树*/ListGet(G.Vertices,j,&x);closeVertex[j].vertex=x;lowCost[j]=-1;谢谢阅读for(i=1;i<n;i++){

/*取结点j*//*保存结点j*//*标记结点j*//*结点寻找当前最小权值的边所对应的弧头K*/minCost=MaxWeight;for(j=0;j<n;j++){if(lowCost[j]<minCost&&lowCost[j]>0)精品文档放心下载{minCost=lowCost[j];k=j;}}ListGet(G.Vertices,k,&x); /*取弧头结点K*/感谢阅读closeVertex[i].vertex=x; /*保存弧头结点K*/谢谢阅读closeVertex[i].weight=minCost; /*保存相应的权值*/感谢阅读lowCost[k]=-1; /*标记结点K*/-//*根据加入集合U的结点K修改lowCost中的数值*/感谢阅读for(j=0;j<n;j++){if(G.edge[k][j]<lowCost[j])感谢阅读lowCost[j]=G.edge[k][j];}}}主文件：prim.cpp#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedefcharVerT;#defineMaxSiz