管道铺设施工的最佳方案问题

...wd......wd......wd...问题描述：实验题目：需要在某个城市n个居民小区之间铺设煤气管道，那么在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽一样。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。基本要求：在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的构造。测试数据：使用以以下图给出的无线网数据作为程序的输入，求出最正确铺设方案。右侧是给出的参考解。简述每一局部的对象、目的和要求：=1\*ROMANI.主函数局部：对象：图G；目的：为图G分配空间，以作为后续调用函数的参数；要求：无。=2\*ROMANII.Create_ALGraph()函数局部：对象：顶点，边及其权值；目的：将顶点，边存放在一起，构成图；要求：构造顶点表，各顶点的邻接表以构造图。=3\*ROMANIII.Create_WLGraph()函数局部：对象：图G；目的：将图中的权值只存放一次，存放到w指向的构造体中；要求：权值只存放一次，再分别存放该边的左右顶点。=4\*ROMANIV.select_info()函数局部：对象：w指向的构造体；目的：将该构造体中的各权值以升序排列；要求：采用简单项选择择法进展排序。=5\*ROMANV.Create_TLGraph()函数局部：对象：排序后的w指向的构造体；目的：找到构成最小生成树的边；要求：依权值升序排列，判断各边是否构成回路来取舍各边。需求分析程序所能到达的基本可能：在n个小区m条管道中，选取n-1条管道，实现连通这n个小区，同时权值之和为最小。输入输出形式及输入值范围：程序运行后，用户可根据提示信息："Pleaseinputtheverticesandtheedges<n,e>:"输入顶点数和边数，再根据提示信息："Pleaseinputtheinformationofthevertices<v>:"输入顶点信息，然后进入循环，创立各个顶点的邻接表，即根据提示信息"Pleaseinputtheinformationofedges<p,q>:"和"Pleaseinputtheinformationofweight:"依次输入各顶点与其他顶点本身以及两者之间的权值，创立图完毕。用户输入完毕后，程序自动输出运行结果。输入值必须为字母和浮点数，可以不必区分大小写。测试数据要求：用户输入字母时，输入大写或小写，都可以被该程序识别，正常运行。但必须根据提示信息后面给出的参考形式，有针对性地输入逗号。概要设计为了实现上述功能，该程序以邻接表来存储图，因此需要图这个抽象数据类型。图抽象数据类型定义：ADTALGraph{数据对象：D={，i=1,2,3....,n,n}数据关系：R=;基本操作：Create_ALGraph(G)；//创立图Create_WLGraph(G)；//将图G中各顶点以及权值存放到新图中，权值只存放一次select_info(W,G)；//将新图W中的权值按升序排列Create_TLGraph(w,G)；//将最小生成树以顶点对〔i,j〕的形式输出}ADTALGraph2.本程序保护模块：主函数模块图模块调用关系：3.主要算法流程图：Create_ALGraph()算法流程图：Create_WLGraph()算法流程图：Create_TLGraph()算法流程图：详细设计相关头文件的调用说明：#include<stdio.h>#include<stdlib.h>#defineMaxVerNum1002.元素类型、结点类型和结点指针类型：staticvoidforcefloat(float*p){floatf=*p;forcefloat(&f);}typedefstructnode{intadjvex;floatinfo;structnode*next;}EdgeNode;typedefstructvnode{charvertex;EdgeNode*firstedge;}VertexNode;typedefVertexNodeAdjList[MaxVerNum];structbian{intz,y;floatinfo;};typedefstruct{charv[MaxVerNum];structbiane[MaxVerNum];}WGraph;structvisit{visited[MaxVerNum];position[MaxVerNum];vvpp[MaxVerNum][MaxVerNum];}3.邻接表类型：typedefstruct {AdjListadjlist; intn,e; }ALGraph;//局部基本操作的伪码实现Create_ALGraph(ALGraph*G){inti,j;charp,q;intk;/*intx=0;*/EdgeNode*s;chara,b;printf("Pleaseinputtheverticesandtheedges<n,e>:\n");scanf("%d,%d",&(G->n),&(G->e));printf("Pleaseinputtheinformationofthevertices<v>:\n");getchar();for(i=0;i<(G->n);i++){scanf("%c",&(G->adjlist[i].vertex));G->adjlist[i].firstedge=NULL;/*if(G->adjlist[i].vertex!=''&&G->adjlist[i].vertex!='\n'&&G->adjlist[i].vertex!=' ')x++;*/}for(k=0;k<2*(G->e);k++){printf("Pleaseinputtheinformationofedges<p,q>:\n");getchar();scanf("%c,%c",&p,&q);s=(EdgeNode*)malloc(sizeof(EdgeNode));s->adjvex=q-64;i=p-64;getchar();printf("Pleaseinputtheinformationofweight:\n");scanf("%f",&(s->info));s->next=G->adjlist[i-1].firstedge;G->adjlist[i-1].firstedge=s;}/*printf("Pleaseoutputtheinformation:\n");printf("%d,%d\n",G->n,G->e);printf("x=%d\n",x);for(i=0;i<G->n;i++){printf("%c\n",G->adjlist[i].vertex);s=G->adjlist[i].firstedge;while(s!=NULL){printf("thelinbianis%d,theinfois%.1f\n",s->adjvex,s->info);s=s->next;}}*/}intPanduan_Vertex(intk,inti,WGraph*w,EdgeNode*s){intt;for(t=0;t<k;t++)if((w->e[t]).y==i+1&&(w->e[t]).z==s->adjvex)return1;return0;}voidselect_info(WGraph*W,ALGraph*G){inti,j,p,k;floatt;for(i=0;i<(G->e);i++){p=i;for(j=i+1;j<(G->e);j++)if(W->e[j].info<W->e[p].info)p=j;if(p!=i){t=W->e[p].info;W->e[p].info=W->e[i].info;W->e[i].info=t;k=W->e[p].z;W->e[p].z=W->e[i].z;W->e[i].z=k;k=W->e[p].y;W->e[p].y=W->e[i].y;W->e[i].y=k;}}/*for(i=0;i<(G->e);i++)printf("%.1f",W->e[i].info);printf("\n");*/}intjudge_vertex(WGraph*w,inti,structvisit*vp){if(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==-1)return1;elseif(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==1)return2;elseif(vp->visited[w->e[i].y-1]==-1&&vp->visited[w->e[i].z-1]==1)return3;elseif(vp->visited[w->e[i].z-1]==1&&vp->visited[w->e[i].y-1]==1)return4;}voidCreate_TLGraph(WGraph*w,ALGraph*G){WGraphT;inti,j,t,h,k=2;intm=1;intabc,bcd;structvisit*vp;vp=(structvisit*)malloc(sizeof(structvisit));for(i=0;i<(G->n);i++){vp->visited[i]=-1;vp->position[i]=-1;vp->vvpp[i][0]=i+1;for(j=1;j<G->n;j++)vp->vvpp[i][j]=0;}T.v[0]=w->v[w->e[0].z-1];T.v[1]=w->v[w->e[0].y-1];vp->visited[w->e[0].z-1]=1;vp->position[w->e[0].z-1]=w->e[0].z;for(j=0;j<(G->n);j++)if(vp->vvpp[w->e[0].z-1][j]==0){vp->vvpp[w->e[0].z-1][j]=w->e[0].y;break;}vp->visited[w->e[0].y-1]=1;vp->position[w->e[0].y-1]=w->e[0].z;T.e[0].info=w->e[0].info;T.e[0].z=w->e[0].z;T.e[0].y=w->e[0].y;for(i=1;i<(G->e);i++){t=judge_vertex(w,i,vp);if(t==4){if(vp->position[w->e[i].z-1]==vp->position[w->e[i].y-1])continue; else{abc=0;bcd=0; for(j=0;j<G->n;j++) if(vp->vvpp[vp->position[w->e[i].y-1]-1][j]!=0) abc++; for(j=0;j<G->n;j++) if(vp->vvpp[vp->position[w->e[i].z-1]-1][j]!=0) bcd++; for(j=bcd,h=0;j<G->n&&h<abc;j++,h++) {vp->vvpp[(vp->position[w->e[i].z-1])-1][j]=vp->vvpp[(vp->position[w->e[i].y-1])-1][h];vp->vvpp[vp->position[w->e[i].y-1]-1][h]=0; } for(h=bcd;h<abc+bcd;h++) vp->position[(vp->vvpp[vp->position[w->e[i].z-1]-1][h])-1]=vp->position[w->e[i].z-1]; T.e[m].info=w->e[i].info;T.e[m].z=w->e[i].z;T.e[m].y=w->e[i].y;m++; }}elseif(t==1) {vp->visited[w->e[i].z-1]=1; vp->visited[w->e[i].y-1]=1; T.v[k++]=w->v[w->e[i].z-1]; T.v[k++]=w->v[w->e[i].y-1];T.e[m].info=w->e[i].info;T.e[m].z=w->e[i].z;T.e[m].y=w->e[i].y;m++; vp->position[w->e[i].z-1]=w->e[i].z;vp->position[w->e[i].y-1]=w->e[i].z; vp->vvpp[w->e[i].z-1][1]=w->e[i].y; vp->vvpp[w->e[i].y-1][0]=0;}elseif(t==2){vp->visited[w->e[i].z-1]=1;vp->position[w->e[i].z-1]=vp->position[w->e[i].y-1];for(j=0;j<(G->n);j++) if(vp->vvpp[vp->position[w->e[i].y-1]-1][j]==0) {vp->vvpp[vp->position[w->e[i].y-1]-1][j]=w->e[i].z; break; } vp->vvpp[w->e[i].z-1][0]=0; T.v[k++]=w->v[w->e[i].z-1]; T.e[m].info=w->e[i].info;T.e[m].z=w->e[i].z;T.e[m].y=w->e[i].y;m++;}elseif(t==3){vp->visited[w->e[i].y-1]=1;vp->position[w->e[i].y-1]=vp->position[w->e[i].z-1];for(j=0;j<(G->n);j++) if(vp->vvpp[vp->position[w->e[i].z-1]-1][j]==0) {vp->vvpp[vp->position[w->e[i].z-1]-1][j]=w->e[i].y; break; } vp->vvpp[w->e[i].y-1][0]=0; T.v[k++]=w->v[w->e[i].y-1]; T.e[m].info=w->e[i].info;T.e[m].z=w->e[i].z;T.e[m].y=w->e[i].y;m++; }}printf("Pleaseoutputtheinformation:\n");for(i=0;i<(G->n)-1;i++)printf("(%c,%c)\n",T.e[i].z+64,T.e[i].y+64);}voidCreate_WLGraph(ALGraph*G){inti,j,t,m,k=0;EdgeNode*s,*p;WGraph*W;W=(WGraph*)malloc(sizeof(WGraph));W->v[0]=G->adjlist[0].vertex;s=G->adjlist[0].firstedge;while(s!=NULL){W->e[k].z=1;W->e[k].y=s->adjvex;W->e[k].info=s->info;k++;s=s->next;}for(i=1;i<(G->n);i++){W->v[i]=G->adjlist[i].vertex;s=G->adjlist[i].firstedge;while(s!=NULL){m=Panduan_Vertex(k,i,W,s);if(m==1){s=s->next;continue;}else{W->e[k].z=i+1;W->e[k].y=s->adjvex;W->e[k].info=s->info;k++;s=s->next;}}}/*printf("Pleaseoutputtheinformation:\n");for(i=0;i<G->n;i++)printf("%c\n",W->v[i]);for(i=0;i<G->e;i++)printf("%d,%d,%.1f\n",W->e[i].z,W->e[i].y,W->e[i].info);*/select_info(W,G);Create_TLGraph(W,G);}主函数的伪码：main(){ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph));Create_ALGraph(G);Create_WLGraph(G);}5.函数调用关系：五．调试分析1.出现问题及解决方法：在刚开场写程序时，由于考虑不全面，在去除连通图闭合回路的算法中遇到很大困难，后来采用以下方法解决了这个问题：将每个顶点分别放在一个构造体中，构造体中的数组visited[i]记录顶点Vi是否被访问过的情况，position[i]记录顶点Vi的具体位置，二维数组vvpp[i][j]记录已经将以该顶点为左顶点或右顶点的权值存入T中后，该权值的右顶点或左顶点的编号。其具体思想是：只要将一个权值存入T中，就将相应的左右顶点放到同一个二维数组中，之后每欲将一个权值参加T中，先检验该权值的两顶点是否在同一个二维数组中。假设不在，那么将该权值存入T中；假设在，将该权值舍去〔因为再将该权值参加T中，就会出现回路〕。方法优缺点分析：优点：=1\*GB3①思想比较简单，容易令人理解；=2\*GB3②在写核心算法时，先将字母顶点用相应的数字代替，所以在将数字转化成字母回去时，利用数字与ASCII码值的固定差值，可以保证用户在输入时的大小写字母都可以被该程序识别。缺点：由于采用数字来代替字母，中间的转换关系比较复杂，尤其是将对应关系理清需要足够的耐心和细心。3．主要算法的时间和空间复杂度分析：〔1〕由于Create_ALGraph()算法中将读入顶点的操作执行了n次，读入边的操作执行了2m次，故其时间复杂度为O〔n+2m〕；〔2〕由于Create_WLGraph()算法将读入权值及其左右顶点的操作执行了n次，故其时间复杂度为O〔n〕；〔3〕由于Create_TLGraph()算法中根据判断是否构成回路来取舍边，因为有n条边，故要执行n次，所以时间复杂度是O〔n〕；〔4〕由于select_info()函数采用简单项选择择法排序，时间复杂度是O〔〕；〔5〕所有算法的空间复杂度都是O〔1〕。六．使用说明程序运行后，用户根据提示输入顶点数，边数，顶点信息，边的信息，权值，输入完毕后程序会自动以顶点对〔i,j〕的形式输出最小生成树的边。七．调试结果输入数据：“9〞，“15〞，“ABCDEFGHI〞，“A,B〞，“32.8〞，“A,C〞，“44.6〞，“A,H〞，“12.1〞，“A,I〞，“18.2〞，“B,A〞，“32.8〞，“B,C〞，“5.9〞，“C,A〞，“44.6〞，“C,B〞，“5.9〞，“C,D〞，“21.3〞，“C,E〞，“41.1〞，“C,G〞，“56.4〞，“D,C〞，“21.3〞，“D,E〞，“67.3〞，“D,F〞，“98.7〞，“E,C〞，“41.1〞，“E,D〞，“67.3〞，“E,F〞，“85.6〞，“E,G〞，“10.5〞，“F,D〞，“98.7〞，“F,E〞，“85.6〞，“F,I〞，“79.2〞，“G,C〞，“56.4〞，“G,E〞，“10.5〞，“G,H〞，“52.5〞，“H,A〞，“12.1〞，“H,G〞，“52.5〞，“H,I〞，“8.7〞，“I,A〞，“18.2〞，“I,F〞，“79.2〞，“I,H〞，“8.7〞。(双引号不需输入)输出数据：(B,C),(H,I),(E,G),(A,H),(C,D),(A,B),(C,E),(F,I)运行结果截屏：八．附录源程序清单：#include<stdio.h>/*调用的头文件库说明*/#include<stdlib.h>#defineMaxVerNum100staticvoidforcefloat(float*p){floatf=*p;/*由于我的TC中不支持浮点数，故添加了这个程序段*/forcefloat(&f);}typedefstructnode/*构造邻接表的构造体*/{intadjvex;floatinfo;/*存放权值*/structnode*next;/*指向下一个邻接点的指针域*/}EdgeNode;typedefstructvnode/*构造顶点表的构造体*/{charvertex;/*顶点域*/EdgeNode*firstedge;/*边表头指针*/}VertexNode;typedefVertexNodeAdjList[MaxVerNum];typedefstruct/*构造图的构造体*/ {AdjListadjlist;/*邻接表*/ intn,e;/*顶点数和边数*/ }ALGraph;structbian/*存放权值及其左右顶点的构造体*/{intz,y;floatinfo;};typedefstruct/*用该构造体来只存放一次权值及其相应的顶点*/{charv[MaxVerNum];structbiane[MaxVerNum];}WGraph;structvisit/*用该构造体来存放各结点被访问的情况，{visited[MaxVerNum];位置，和其他结点的关系*/position[MaxVerNum];vvpp[MaxVerNum][MaxVerNum];}Create_ALGraph(ALGraph*G)/*创立图*/{inti,j;charp,q;intk;EdgeNode*s;chara,b;printf("Pleaseinputtheverticesandtheedges<n,e>:\n");/*输入顶点数和边数*/scanf("%d,%d",&(G->n),&(G->e));printf("Pleaseinputtheinformationofthevertices<v>:\n");getchar();for(i=0;i<(G->n);i++)/*建设有n各顶点的顶点表*/{scanf("%c",&(G->adjlist[i].vertex));/*读入顶点信息*/G->adjlist[i].firstedge=NULL;}for(k=0;k<2*(G->e);k++)/*建设边表*/{printf("Pleaseinputtheinformationofedges<p,q>:\n");getchar();scanf("%c,%c",&p,&q);/*读入边的顶点*/s=(EdgeNode*)malloc(sizeof(EdgeNode));s->adjvex=q-64;/*邻接点的序号为q-64*/i=p-64;getchar();printf("Pleaseinputtheinformationofweight:\n");/*读入权值*/scanf("%f",&(s->info));s->next=G->adjlist[i-1].firstedge;/*将新边表结点s插入到顶点Vi的边表头部*/G->adjlist[i-1].firstedge=s;}}intPanduan_Vertex(intk,inti,WGraph*w,EdgeNode*s)/*判断该边是不是已经读入到w指{intt;向的构造体中*/for(t=0;t<k;t++)if((w->e[t]).y==i+1&&(w->e[t]).z==s->adjvex)return1;return0;}voidselect_info(WGraph*W,ALGraph*G)/*将w指向的构造体中各权值按升序{inti,j,p,k;排列*/floatt;for(i=0;i<(G->e);i++)/*简单项选择择排序*/{p=i;for(j=i+1;j<(G->e);j++)if(W->e[j].info<W->e[p].info)p=j;if(p!=i){t=W->e[p].info;/*将两条边的权值左右顶点都进展交换*/W->e[p].info=W->e[i].info;W->e[i].info=t;k=W->e[p].z;W->e[p].z=W->e[i].z;W->e[i].z=k;k=W->e[p].y;W->e[p].y=W->e[i].y;W->e[i].y=k;}}/*for(i=0;i<(G->e);i++)printf("%.1f",W->e[i].info);printf("\n");*/}intjudge_vertex(WGraph*w,inti,structvisit*vp)/*判断顶点的访问情况*/{if(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==-1)return1;elseif(vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==1)return2;elseif(vp->visited[w->e[i].y-1]==-1&&vp->visited[w->e[i].z-1]==1)return3;elseif(vp->visited[w->e[i].z-1]==1&&vp->visited[w->e[i].y-1]==1)return4;}voidCreate_TLGraph(WGraph*w,ALGraph*G)/*生成最小生成树*/{WGraphT;inti,j,t,h,k=2;intm=1;intabc,bcd;structvisit*vp;vp=(structvisit*)malloc(sizeof(structvisit));for(i=0;i<(G->n);i++)/*将各顶点的被访问情况，位置，与其他顶点{vp->visited[i]=-1;的相互关系进展初始化*/vp->position[i]=-1;vp->vvpp[i][0]=i+1;for(j=1;j<G->n;j++)vp->vvpp[i][j]=0;}T.v[0]=w->v[w->e[0].z-1];T.v[1]=w->v[w->e[0].y-1];vp->visited[w->e[0].z-1]=1;vp->position[w->e[0].z-1]=w->e[0].z;for(j=0;j<(G->n);j++)if(vp->vvpp[w->e[0].z-1][j]==0){vp->vvpp[w->e[0].z-1][j]=w->e[0].y;break;}vp->visited[w->e[0].y-1]=1;vp->position[w->e[0].y-1]=w->e[0].z;T.e[0].info=w->e[0].info;T.e[0].z=w->e[0].z;T.e[0].y=w->e[0].y;for(i=1;i<(G->e);i++){t=judge_vertex(w,i,vp);/*根据不同的顶点访问情况选取相应操作*/if(t==4)/*两顶点均已被访问过的情况*/{if(vp->position[w->e[i].z-1]==vp->position[w->e[i].y-1])/*两顶点位置一样*/continue;/*舍去这条边，否那么会构成回路*/ else{abc=0;bcd=0;/*倘假设两顶点位置不同*/ for(j=0;j<G->n;j++) if(vp->vvpp[vp->position[w->e[i].y-1]-1][j]!=0) abc++; for(j=0;j<G->n;j++) if(vp->vvpp[vp->position[w->e[i].z-1]-1][j]!=0) bcd++; for(j=bcd,h=0;j<G->n&&h<abc;j++,h++)将两顶点放在同一个数组中*/ {vp->vvpp[(vp->position[w->e[i].z-1])-1][j]=vp->vvpp[(vp->position[w->e[i].y-1])-1][h];vp->vvpp[vp->position[w->e[i].y-1]-1][h]=0;/*将原数组置零*/ } for(h=bcd;h<abc+bcd;h++) vp->position[(vp->vvpp[vp->position[w->e[i].z-1]-1][h])-1]=vp->position[w->e[i].z-1]; T.e[m].info=w->e[i].info;/*将该边存入T中*/T.e[m].z=w->e[i].z;T.e[m].y=w->e[i].y;m++; }}elseif(t==1)/*两顶点都未被访问的情况*/ {vp->visited[w->e[i].z-1]=1; vp->visited[w->e[i].y-1]=1; T.v[k++]=w->v[w->e[i].z-1]; T.v[k++]=w->v[w->e[i].y-1];T.e[m].info=w->e[i].info;/*将该边存入T中*/T.e[m].z=w->e[i].z;T.e[m].y=w->e[i].y;m++; vp->position[w->e[i].z-1]=w->e[i].z;/*将两顶点的位置改为一样*/vp->position[w->e[i].y-1]=w->e[i].z; vp->vvpp[w->e[i].z-1][1]=w->e[i].y;/*将两顶点存放到一个数组中*/ vp->vvpp[w->e[i].y-1][0]=0;}elseif(t==2)/*左顶点未被访问，右顶点已被访问的情况*/{vp->visited[w->e[i].z-1]=1;vp->position[w->e[i].z-1]=vp->position[w->e[i].y-1];/*将左顶点的位置改为右顶点的位置*/for(j=0;j<(G->n);j++)/*将两顶点存放到一个数组中*/ if(vp->vvpp[vp->position[w->e[i].y-1]-1][j]==0) {vp->vvpp[vp->position[w->e[i].y-1]-1][j]=w->e[i].z; break; } vp->vvpp[w->e[i].z-1][0]=0; T.v[k++]=w->v[w