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

1一．问题描述：1.实验题目：需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。2.基本要求：在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。3.测试数据：使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。4.简述每一部分的对象、目的和要求：I.主函数部分：对象：图G；目的：为图G分配空间，以作为后续调用函数的参数；2要求：无。II.Create_ALGraph()函数部分：对象：顶点，边及其权值；目的：将顶点，边存放在一起，构成图；要求：构造顶点表，各顶点的邻接表以构造图。III.Create_WLGraph()函数部分：对象：图G；目的：将图中的权值只存放一次，存放到w指向的结构体中；要求：权值只存放一次，再分别存放该边的左右顶点。IV.select_info()函数部分：对象：w指向的结构体；目的：将该结构体中的各权值以升序排列；要求：采用简单选择法进行排序。V.Create_TLGraph()函数部分：对象：排序后的w指向的结构体；目的：找到构成最小生成树的边；要求：依权值升序排列，判断各边是否构成回路来取舍各边。二．需求分析1.程序所能达到的基本可能：在n个小区m条管道中，选取n-1条管道，实现连通这n个小区，同时权值之和为最小。2.输入输出形式及输入值范围：程序运行后，用户可根据提示信息：Pleaseinputtheverticesandtheedgesn,e:输入顶点数和边数，再根据提示信息：Pleaseinputtheinformationoftheverticesv:输入顶点信息，然后进入循环，创建各个顶点的邻接表，即根据提示信息Pleaseinputtheinformationofedgesp,q:和Pleaseinputtheinformationofweight:依次输入各顶点与其他顶点本身以及两者之间的权值，创建图完毕。用户输入完毕后，程序自动输出运行结果。输入值必须为字母和浮点数，可以不必区分大小写。3.测试数据要求：3用户输入字母时，输入大写或小写，都可以被该程序识别，正常运行。但必须根据提示信息后面给出的参考形式，有针对性地输入逗号。三．概要设计为了实现上述功能，该程序以邻接表来存储图，因此需要图这个抽象数据类型。1.图抽象数据类型定义：ADTALGraph{数据对象：D={iibAdjList,|,,aiiiacbintint,ic，i=1,2,3....,n,n0}数据关系：R=;基本操作：Create_ALGraph(G)；//创建图Create_WLGraph(G)；//将图G中各顶点以及权值存放到新图中，权值只存放一次select_info(W,G)；//将新图W中的权值按升序排列Create_TLGraph(w,G)；//将最小生成树以顶点对（i,j）的形式输出}ADTALGraph2.本程序保护模块：主函数模块图模块调用关系：主函数模块图模块3.主要算法流程图：4Create_ALGraph()算法流程图：Create_WLGraph()算法流程图：开始读入顶点数和边数i=0in读入顶点信息i=i+1K=0K2e读入边Vi,Vj的对应顶点及权值将新边表结点插入到顶点Vi的边表头部k=k+1结束TFFT开始i=0in该权值还未存入W中读入该权值及左右顶点编号i=i+1结束s！=NULLs=s-nextTFTFTF5Create_TLGraph()算法流程图：开始初始化存储各顶点被访问情况及位置信息的结构体指针vpi=1调用judge_vertex()函数若两顶点都已被访问过若两顶点位置不同将该权值加入T中，并把位置改相同若左顶点未被访问，右顶点已被访问若左顶点已被访问，右顶点未被访问若两顶点都未被访问将该权值加入T中，并把左顶点的位置改为和右顶点相同将该权值加入T中，并把右顶点的位置改为和左顶点相同将该权值加入T中，并把两顶点的位置改为相同i=i+1ie输出最小生成树的各边结束6四．详细设计1.相关头文件的调用说明：#includestdio.h#includestdlib.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;structvisit7{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(Pleaseinputtheverticesandtheedgesn,e:\n);scanf(%d,%d,&(G-n),&(G-e));printf(Pleaseinputtheinformationoftheverticesv:\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;k2*(G-e);k++){printf(Pleaseinputtheinformationofedgesp,q:\n);getchar();scanf(%c,%c,&p,&q);8s=(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;iG-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;tk;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;9floatt;for(i=0;i(G-e);i++){p=i;for(j=i+1;j(G-e);j++)if(W-e[j].infoW-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)10return4;}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;jG-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);11if(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;jG-n;j++)if(vp-vvpp[vp-position[w-e[i].y-1]-1][j]!=0)abc++;for(j=0;jG-n;j++)if(vp-vvpp[vp-position[w-e[i].z-1]-1][j]!=0)