建立n个城市间的最小生成树.docx
- 文档编号:9927439
- 上传时间:2023-05-22
- 格式:DOCX
- 页数:28
- 大小:83.48KB
建立n个城市间的最小生成树.docx
《建立n个城市间的最小生成树.docx》由会员分享,可在线阅读,更多相关《建立n个城市间的最小生成树.docx(28页珍藏版)》请在冰点文库上搜索。
建立n个城市间的最小生成树
1设计要求
1.1问题重述
选择6-10个城市模拟在城市之间建立通信网络,只需要架设通信路线就可以,以最低的经济花费建设通信网,即用Prim算法或Kreskas算法生成一个网的最小生成树,并计算得到的最小生成树的代价。
1.2基本要求
◆城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本上的定义,若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。
要求在屏幕上显示得到的最小生成树中包括那些城市间的道路,并显示得到的最小生成树的代价。
◆表示城市间距离网的邻接矩阵
◆最小生成树中包括的边及其权值,并显示得到的最小生成树的代价。
2概要设计
为了实现以上功能,可以从以下主界面构造、存储结构采用、系统功能设置等三个方面进行分析设计。
将图的结点信息存放在一个顺序表中,图的边信息存储在一个二维数组edge[MaxVertices][MaxVertices]中,这样就实现了用邻接矩阵存放城市间的距离网。
在Prim算法的函数用两个参数,一个是图G为邻接矩阵存储结构的图;另一个是通过函数得到的最小生成树的结点数据和相应结点的边的权值数据closeVertex.
2.1主界面的设计
为了首先需要设计一个主界面子程序,以链接系统的各项子功能运行界面如图1所示
图1
2.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.1n个城市连接的最小生成树
选择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”邻接矩阵存储结构存放边的信息
a.初始化图G,n为结点个数。
Initiate(AdjMGraph*G,intn)
b.在图G中插入结点vertex
InsertVertex(AdjMGraph*G,DataTypevertex)
c.在图G中插入边
InsertEdge(AdjMGraph*G,intv1,intv2,intweight)
d.在图G中删除边
DeleteEdge(AdjMGraph*G,intv1,intv2)
e.删除图G中的结点v以及与该节点相关的所有边
DeleteVerten(AdjMGraph*G,intv)
f.在图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后的状态。
lowcostlowcostlowcostlowcostlowcost
lowcostlowcost
3.4算法描述
3.4.1流程图
创建用邻接矩阵表示的城市道路网
输入城市属N=7
道路数e=20
输入城市a[]
输入表示两个城市间距离
RowColWeightrcw[]
返回
图2创建邻接矩阵流程图
判断程序是否为真
Prim算法
用铺助数组lowCost[]
输入初始城市序号j
for(i=1;i lowCost[i]=G.edge[j][i]从结点O出发构造最小生成树 结点寻找当前最小权值的边所对应的弧头 minCost=MaxWeight 输出找到的道路 标记城市 输出总代价 判断是否继续: 1-继续;2-退出 1: 返回程序开始处 2: 退出 结束 Prim算法流程图 4测试结果及分析 4.1测试结果 4.2结果分析 当从一个第一个顶点开始以此作为生成树的初始状态,然后找出与其之间权值最小的顶点2并把顶点2添加到该生成树中,以此类推找出与顶点2之间权值最小的顶点。 再把找出的顶点添加到生成树中直到最后一个顶点添加到生成树上是得到所求的生成数即为最小生成树。 4.3错误分析 在本次课程设计的过程中,出现诸多错误,比如分号没有打以及一些错打和少打的情况,在此不做一一的介绍,只介绍一些较大的错误。 1、本应从任一节点接入均可以构造最小生成树,所以在运行普利姆算法时需要在创建数组之前输入一个城市的结点序号,在开始时,只是将数组中的j写入,并没有赋初始值,所以在程序运行时出现了错误。 2、在成功运行从任意结点构造生成树后,由于需要关闭运行框后才能进行下一次的构造,这是在实际运行中是不允许的,所以要求在程序开始时加一个判断语句,只要在执行完后进行是否继续的判断就可以直接再次运行普利姆算法而不需要关闭运行框后再重新运行程序。 5源程序 头文件: AdjMGraph.h typedefintDataType; 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->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 for(j=0;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)/*v在图G中插入结点vertex*/ { ListInsert(&G->Vertices,G->Vertices.size,vertex);/*顺序表尾插入*/ } voidInsertEdge(AdjMGraph*G,intv1,intv2,intweight) /*在图G中插入边 { 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中删除边 { 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 for(j=0;j if((i==v||j==v)&&G->edge[i][j]>0&&G->edge[i][j] G->numOfEdges--;/*计算被删除边*/ for(i=v;i for(j=0;j G->edge[i][j]=G->edge[i+1][j]; for(i=0;i for(j=v;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 if(G.edge[v][col]>0&&G.edge[v][col] 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 if(G.edge[v1][col]>0&&G.edge[v1][col] 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 InsertVertex(G,V[i]);/*结点插入*/ for(k=0;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 lowCost[i]=G.edge[j][i]; /*从结点j出发构造最小生成树*/ ListGet(G.Vertices,j,&x);/*取结点j*/ closeVertex[j].vertex=x;/*保存结点j*/ lowCost[j]=-1;/*标记结点j*/
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 建立 城市 最小 生成