《数据结构课程设计》建立通信网络

《数据结构课程设计》建立通信网络在n个城市建设通信网络，只需架设n-1条线路即可。设计算法，求出如果以最低的经济代价建设这个通信网络。要求如下：至少包含10个城市；城市数n由键盘录入；城市坐标由随机函数产生小于100的整数；输出生成树中各条边以及它们的权值；1．课程设计目的通过做实验报告，发现问题，解决问题来熟练掌握图的定义、储存结构和邻接矩阵表示方法等等，再用kruskal算法和prim算法来实现求最小生成树的权值，再把它运用到现实生活当中去.2．需求分析2.1问题描述：要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济建设这个通信网，是一个网的最小生成树。2.2设计要求：可以用连通网来表示n个城市间可能设置的通信网络，其中网的顶点表示城市，边表示两城市之间的路线，边的权值表示相应的费用。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一棵生成树，它使总的费用最少，这棵树就是最小生成树。一棵生成树的费用就是树上各边的费用之和。本程序的目的是要建设一个最经济的通信网，根据用户输入的网，输出相应的最小生成树。在这里城市以及两城市之间的费用都用整型数来代替。利用克鲁斯卡尔算法和普利姆算法实现。①克鲁斯卡尔算法：要求设计程序输入如下：(1)图的顶点可以输入数字或字母，连着输入，之间不需要空格。（2）必须按规格输入相应的邻接矩阵，否则会出错。程序所能达到的功能：直接实现最小生成树权值的计算。②普利姆算法:要求设计程序输入如下：(1)数据城市间的距离网采用邻接矩阵表示。（2）若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。（3）输入图的顶点可以只能是数字，不能是字母，不然会出错。程序所能达到的功能：屏幕显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的权值之和。3．概要设计3.1概要问题分析：（1）最小生成树的定义：对于一个带权（假定每条边上的权值均大于零的实数）连通无向图G中的不同生成树，其每棵树的所有边上的权值之和也可能不同；图的所有生成树中的具有边上的权值之和最小的树成为图的最小生成树。（2）最小生成树的典型用途：欲在n个城市间建立通信网.n个城市可能有n(n-1)/2条线路，但铺n-1条线路即可连通；因为每条线路都会有对应的经济成本，那么，如何选择n–1条线路，使总费用最少？（3）构造数学模型：顶点———表示城市，有n个；边————表示线路，有n–1条；边的权值—表示线路的经济代价；连通网——表示n个城市间通信网。（4）最小生成树的操作：Prim算法：假设G=(V,E)是连通图，T=(U,TE)为欲构造的最小生成树，初始化U={u0}，TE为空，重复以下操作：在所有u∈U,v∈V-U的边(u,v)∈E中，选择一条权最小的边(u,v)并入TE，同时将v并入U，直到U=V为止，此时T=(U,TE)是G的一棵最小生成树。kruskal算法：分e步，其中e是网络中边的数目。按耗费递增的顺序来考虑这e条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。代码采用邻接矩阵表示图，采用边集表示法。3.2概要设计①克鲁斯卡尔算法：1.①定义一个边集结构，用来存储图的所有边信息。②构造邻接矩阵法图的生成函。③MSTEdge数组，用来存储已确定的MST的边的编号，共VertexNum-1条边。④用Kruskal算法生成MST。2.本程序包含6个函数：(1)主函数main()(2)邻接矩阵法图的生成函数voidCreateGraph(Graph*g)(3)打印图的结点标识符和邻接矩阵voidPrintGraph(Graphg)(4)intCalVerNum(Graphg)//图的顶点数(5)intCalEdgNum(Graphg)//获取图的边数(6)voidKruskal(Graphg)//Kruskal算法生成MST②普利姆算法:1.本程序包含6个函数：(1)主函数main()(2)intLocate(MGraph&g,intV)//求顶点位置函数(3)MGraphCreateMap(MGraph&g)//创建图(4)intMin(MGraph&g,Nodeclosest[])//closest[]中权值最小的边(5)voidprim(MGraph&g,intu)//从顶点u出发构造连通图g的最小生成树，并输出生成树的每条(6)voiddisplay(MGraph&g)//输出邻接矩阵算法2.Prim算法流程设计:如图七个城市之间共有11条路，运用Prim算法：选定第一个点⑥，从它closest的边中选择最短边⑥⑦,权值为2；⑥⑤，权值为3；⑥③，权值为5；③①，权值为5；⑤④，权值为6；④②，权值为4；所得最小生成树的权值为2+3+5+5+6+4=25.4详细设计4.1克鲁斯卡尔算法：typedefstructGraph{ //定义图的邻接矩阵表示法结构VertexTypever[MaxSize+1];intedg[MaxSize][MaxSize];}Graph;2.typedefstructgEdge{ //定义一个边集结构，用来存储图的所有边信息intbegin;intend;intweight;}gEdge;(1)主函数intmain(){Graphg;CreateGraph(&g);PrintGraph(g);Kruskal(g);return0;}(2)intCalVerNum(Graphg)//求图的顶点数{returnstrlen(g.ver);}intCalEdgNum(Graphg)//获取图的边数{Graphp=g;intcount=0;intVertexNum=CalVerNum(p);for(inti=0;i<VertexNum;i++)for(intj=i;j<VertexNum;j++) //邻接矩阵对称，计算上三角元素和就可以了if(0!=p.edg[i][j])count++;returncount;}(3)邻接矩阵法图的生成函数：voidCreateGraph(Graph*g){ inti=0; intj=0; intVertexNum; VertexTypeVer; printf("请输入图的顶点:\n"); while('\n'!=(Ver=getchar())){g->ver[i++]=Ver; } g->ver[i]='\0'; VertexNum=strlen(g->ver); printf("请输入相应的的邻接矩阵:\n"); for(i=0;i<VertexNum;i++) for(j=0;j<VertexNum;j++) scanf("%d",&g->edg[i][j]);}(4)打印图的结点标识符和邻接矩阵voidPrintGraph(Graphg){ inti,j; intVertexNum=strlen(g.ver); printf("图的顶点为:\n"); for(i=0;i<VertexNum;i++)printf("%c",g.ver[i]); printf("\n"); printf("图的邻接矩阵为:\n"); for(i=0;i<VertexNum;i++){for(j=0;j<VertexNum;j++) printf("%d",g.edg[i][j]); printf("\n"); }}(5)Kruskal算法生成MSTvoidKruskal(Graphg){ intVertexNum=CalVerNum(g); intEdgNum=CalEdgNum(g); gEdge*p=CreateEdges(g); int*index=(int*)malloc(sizeof(int)*VertexNum); //index数组，其元素为连通分量的编号，index[i]=index[j]表示编号为i和j的顶点在同一个连通分量中，反之则不在同一个连通分量 int*MSTEdge=(int*)malloc(sizeof(int)*VertexNum-1);//MSTEdge数组，用来存储已确定的MST的边的编号，共VertexNum-1条边 intk=0; intWeightSum=0; intIndexBegin,IndexEnd; for(inti=0;i<VertexNum;i++)//初始化所有index=-1 index[i]=-1; for(i=0;i<VertexNum-1;i++){ for(intj=0;j<EdgNum;j++){ if(!(index[p[j].begin]>=0&&index[p[j].end]>=0&&index[p[j].begin]==index[p[j].end])){//找到当前还没加入到同一个连通分量且权值最下的边 MSTEdge[i]=j;//将其加入到MST中去 if((-1==index[p[j].begin])&&(-1==index[p[j].end]))//该边的两个顶点都没加入过任何一个连通分量 index[p[j].begin]=index[p[j].end]=i; elseif((-1==index[p[j].begin])&&(index[p[j].end]>=0)){ //该边的尾end已在一个连通分量，头begin未加入过任何连通分量 index[p[j].begin]=i; IndexEnd=index[p[j].end]; for(intn=0;n<VertexNum;n++) if(index[n]==IndexEnd) index[n]=i;}elseif((-1==index[p[j].end])&&(index[p[j].begin]>=0)){ //该边的头begin已在一个连通分量，尾end未加入过任何连通分量 index[p[j].end]=i; IndexBegin=index[p[j].begin]; for(intn=0;n<VertexNum;n++)if(index[n]==IndexBegin)index[n]=i;}else{IndexEnd=index[p[j].end]; IndexBegin=index[p[j].begin];for(intn=0;n<VertexNum;n++)//该边的两个顶点都已经存在于两个不同的连通分中if(index[n]==IndexBegin||index[n]==IndexEnd) index[n]=i;//将该连通分量编号全部修改为相同的值} break; } } } printf("MST的边为:\n");//输出MST的边 for(i=0;i<VertexNum-1;i++){ printf("%c--%c\n",g.ver[p[MSTEdge[i]].begin],g.ver[p[MSTEdge[i]].end]); WeightSum+=p[MSTEdge[i]].weight; } printf("MST的权值为:%d\n",WeightSum); //输出MST的权值}注：具体源代码见附录4.2普利姆算法:4.2.1主函数：voidmain(){intst;MGraphg;cout<<"\n*********************n个城市的最小生成树*****************"<<endl;CreateMap(g); {cout<<"\n该图所对应的邻接矩阵如下:"<<endl;display(g);cout<<endl<<"请输入起点城市编号:";cin>>st;while(1) {if(st==0)break;elseif(st>g.n)cout<<"输入起点城市编号有错，请重新输入!"<<endl;else {prim(g,st);cout<<"\n*************************************************"<<endl; }cout<<endl<<"请继续输入起点城市,否则输入0退出!"<<endl;cin>>st; } }}4.2.2创建图MGraphCreateMap(MGraph&g){inti,j,k,v1,v2,vex,m=1;cout<<"请输入城市的个数：";cin>>g.n;if(g.n<=1){cout<<"最小生成树不存在!"<<endl;returng;}else{cout<<"请输入城市的边数：";cin>>g.e;for(i=0;i<g.n;i++)//初始化邻接矩阵for(j=0;j<g.n;j++)if(i==j)g.city[i][j].weight=0;elseg.city[i][j].weight=INF;cout<<"请输入城市的顶点编号：";//输入图中的顶点编号for(i=0;i<g.n;i++)cin>>g.vexs[i];cout<<"输入每条边所对应的两个顶点及权值<格式：起点城市终点城市权值>!"<<endl;for(k=0;k<g.e;k++){cout<<"请输入第"<<m++<<"条边：";cin>>v1>>v2>>vex;//输入一条边的两个顶点及权值i=Locate(g,v1);j=Locate(g,v2);g.city[i][j].weight=vex;g.city[j][i].weight=vex;}return(g);}}4.2.3输出邻接矩阵算法voiddisplay(MGraph&g){inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++)if(g.city[i][j].weight==INF)cout<<"\t"<<"∞";elsecout<<"\t"<<g.city[i][j].weight;cout<<endl;}}4.2.4构造连通图g的最小生成树voidprim(MGraph&g,intu)//从顶点u出发,构造连通图g的最小生成树，并输出生成树的每条边{MGraphp;inti,j,k,k0,u0,v0,s=0,n=0;k=Locate(g,u);//k为顶点u的位置p.vexs[n++]=u;closest[k].lowcost=0;//初始化U={u}for(i=0;i<g.n;i++)if(i!=k)//初始化closest[i]{closest[i].vex=u;closest[i].lowcost=g.city[k][i].weight;}for(j=1;j<=g.n-1;j++)//选择其余的n-1条边(n=g.n){k0=Min(g,closest);//closest[k0]中存有当前最小边(u0,v0)的信息u0=closest[k0].vex;//u0∈Uv0=g.vexs[k0];//v0∈V-Up.vexs[n++]=v0;s+=closest[k0].lowcost;//求最小生成树的权值之和cout<<"从编号为"<<u0<<"的城市到编号为"<<v0<<"的城市"<<"的权值为"<<closest[k0].lowcost<<endl;//输出最小生成树的路径closest[k0].lowcost=0;//将顶点v0纳入U集合for(i=0;i<g.n;i++)//在顶点v0并入U之后,重新选择最小边if(g.city[k0][i].weight<closest[i].lowcost){closest[i].lowcost=g.city[k0][i].weight;closest[i].vex=v0;}}cout<<"\n最小生成树的权值之和为："<<s<<endl;}注：具体源代码见附录5调试分析5.1克鲁斯卡尔算法测试当邻接矩阵输入错误是会有如图所示的提示：注意：输入的邻接矩阵必须按规范来，不能多输入一个顶点或少一个顶点。5.2普利姆算法测试手动输入城市顶点个数和邻接矩阵：

5.3测试结果继续输入，换个起点城市编号最小生成树的权值之和也一样6．课程设计总结通过做这次实验报告，让我对数据结构以及C语言的应用有了更深的掌握了解，更是让我认识到了数据结构算法的重要性！！！算法虽然很复杂，让人很难理解，但只要耐下心来一步一步去弄懂每个语句，再运用到实践当中去实现一些功能还是容易熟练掌握的。幸亏自己有一定的C语言基础和离散数学基础，不然去理解最小生成树和邻接矩阵的概念还是挺费劲的。

7．附录（源代码）①克鲁斯卡尔算法：#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMaxSize20typedefcharVertexType;typedefstructGraph{ //定义图的邻接矩阵表示法结构 VertexTypever[MaxSize+1]; intedg[MaxSize][MaxSize];}Graph;typedefstructgEdge{ //定义一个边集结构，用来存储图的所有边信息 intbegin; intend; intweight;}gEdge;voidCreateGraph(Graph*g) //邻接矩阵法图的生成函数{ inti=0; intj=0; intVertexNum; VertexTypeVer; printf("请输入图的顶点:\n"); while('\n'!=(Ver=getchar())){ g->ver[i++]=Ver; } g->ver[i]='\0'; VertexNum=strlen(g->ver); printf("请输入相应的的邻接矩阵:\n"); for(i=0;i<VertexNum;i++) for(j=0;j<VertexNum;j++) scanf("%d",&g->edg[i][j]);}voidPrintGraph(Graphg) //打印图的结点标识符和邻接矩阵{ inti,j; intVertexNum=strlen(g.ver); printf("图的顶点为:\n"); for(i=0;i<VertexNum;i++) printf("%c",g.ver[i]); printf("\n"); printf("图的邻接矩阵为:\n"); for(i=0;i<VertexNum;i++){ for(j=0;j<VertexNum;j++) printf("%d",g.edg[i][j]); printf("\n"); }}intCalVerNum(Graphg) //求图的顶点数{ returnstrlen(g.ver);}intCalEdgNum(Graphg) //获取图的边数{ Graphp=g; intcount=0; intVertexNum=CalVerNum(p); for(inti=0;i<VertexNum;i++) for(intj=i;j<VertexNum;j++) //邻接矩阵对称，计算上三角元素和即可 if(0!=p.edg[i][j]) count++; returncount;}gEdge*CreateEdges(Graphg) //生成图的排序过的边集数组{ inti,j; intk=0; intEdgNum=CalEdgNum(g); intVertexNum=CalVerNum(g); gEdgetemp; gEdge*p=(gEdge*)malloc(sizeof(gEdge)*EdgNum); for(i=0;i<VertexNum;i++) //边集数组初始化,同样只考虑上三角矩阵 for(j=i;j<VertexNum;j++) if(0!=g.edg[i][j]){ p[k].begin=i; p[k].end=j; p[k].weight=g.edg[i][j]; k++; } for(i=0;i<EdgNum-1;i++) //对边集数组进行选择排序 for(j=i+1;j<EdgNum;j++) if(p[i].weight>p[j].weight){ temp=p[i]; p[i]=p[j]; p[j]=temp; } returnp;}//Kruskal算法生成MSTvoidKruskal(Graphg){ intVertexNum=CalVerNum(g); intEdgNum=CalEdgNum(g); gEdge*p=CreateEdges(g); int*index=(int*)malloc(sizeof(int)*VertexNum); //index数组，其元素为连通分量的编号，index[i]=index[j]表示编号为i和j的顶点在同一个连通分量中，反之则不在同一个连通分量 int*MSTEdge=(int*)malloc(sizeof(int)*VertexNum-1); //MSTEdge数组，用来存储已确定的MST的边的编号，共VertexNum-1条边 intk=0; intWeightSum=0; intIndexBegin,IndexEnd; for(inti=0;i<VertexNum;i++) //初始化所有index=-1 index[i]=-1; for(i=0;i<VertexNum-1;i++){ for(intj=0;j<EdgNum;j++){ if(!(index[p[j].begin]>=0&&index[p[j].end]>=0&&index[p[j].begin]==index[p[j].end])){//找到当前还没加入到同一个连通分量且权值最下的边 MSTEdge[i]=j; //将其加入到MST中去 if((-1==index[p[j].begin])&&(-1==index[p[j].end])) //该边的两个顶点都没加入过任何一个连通分量 index[p[j].begin]=index[p[j].end]=i; elseif((-1==index[p[j].begin])&&(index[p[j].end]>=0)){ //该边的尾end已在一个连通分量，头begin未加入过任何连通分量 index[p[j].begin]=i; IndexEnd=index[p[j].end]; for(intn=0;n<VertexNum;n++) if(index[n]==IndexEnd) index[n]=i; } elseif((-1==index[p[j].end])&&(index[p[j].begin]>=0)){ //该边的头begin已在一个连通分量，尾end未加入过任何连通分量 index[p[j].end]=i; IndexBegin=index[p[j].begin]; for(intn=0;n<VertexNum;n++) if(index[n]==IndexBegin) index[n]=i; } else{ IndexEnd=index[p[j].end]; IndexBegin=index[p[j].begin]; for(intn=0;n<VertexNum;n++) //该边的两个顶点都已经存在于两个不同的连通分量中 if(index[n]==IndexBegin||index[n]==IndexEnd) index[n]=i; //将该连通分量编号全部修改为相同的值 } break; } } } printf("MST的边为:\n"); //输出MST的边 for(i=0;i<VertexNum-1;i++){ printf("%c--%c\n",g.ver[p[MSTEdge[i]].begin],g.ver[p[MSTEdge[i]].end]); WeightSum+=p[MSTEdge[i]].weight; } printf("MST的权值为:%d\n",WeightSum); //输出MST的权值}intmain(){ Graphg; CreateGraph(&g); PrintGraph(g); Kruskal(g); return0;}②普利姆算法:#include<iostream.h>#include<stdio.h>#include<string.h>#include<malloc.h>constintMAXV=30;//最多顶点个数constintINF=32768;//表示极大值，即∞structNode{intweight;intvex;//存放顶点编号intlowcost;//存放顶点权值};structMGraph{intvexs[MAXV],n,e;//vexs表示顶点向量;n,e分别表示图的顶点数和边数Nodecity[MAXV][MAXV];//邻接矩阵};Nodeclosest[MAXV];//求最小生成树时的辅助数组intLocate(MGraph&g,intV)//求顶点位置函数{intj=-1,k;for(k=0;k<g.n;k++)if(g.vexs[k]==V) {j=k;break; }returnj;}MGraphCreateMap(MGraph&g)//创建图{inti,j,k,v1,v2,vex,m=1;cout<<"请输入城市的个数：";cin>>g.n;if(g.n<=1) {cout<<"最小生成树不存在!"<<endl;returng; }else {cout<<"请输入城市的边数：";cin>>g.e;for(i=0;i<g.n;i++)//初始化邻接矩阵for(j=0;j<g.n;j++)if(i==j)g.city[i][j].weight=0;elseg.city[i][j].weight=INF;cout<<"请输入城市的顶点编号：";//输入图中的顶点编号for(i=0;i<g.n;i++)cin>>g.vexs[i];cout<<"输入每条边所对应的两个顶点及权值<格式：起点城市终点城市权值>!"<<endl;for(k=0;k<g.e;k++) {cout<<"请输入第"<<m++<<"条边：";cin>>v1>>v2>>vex;//输入一条边的两个顶点及权值i=Locate(g,v1);j=Locate(g,v2);g.city[i][j].weight=vex;g.city[j][i].weight=vex; }return(g); }}intMin(MGraph&g,Nodeclosest[])//closest[]中权值最小的边{inti,min,j;min=INF;for(i=0;i<g.n;i++)if(closest[i].lowcost<min&&closest[i].lowcost!=0) {min=closest[i].lowcost;j=i; }returnj;//返回权值最小的边在辅助数组中的位置}voidprim(MGraph&g,intu)//从顶点u出发,按普里姆算法构造连通图g的最小生成树，并输出生成树的每条边{MGraphp;inti,j,k,k0,u0,v0,s=0,n=0;k=Locate(g,u);//k为顶点u的位置p.vexs[n++]=u;closest[k].lowcost=0;//初始化U={u}for(i=0;i<g.n;i++)if(i!=k)//初始化closest[i] {closest[i].vex=u;closest[i].lowcost=g.city[k][i].weight;