《管道铺设施工的最佳方案》由会员分享，可在线阅读，更多相关《管道铺设施工的最佳方案（7页珍藏版）》请在装配图网上搜索。
1、1）内容：需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺 设n-1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不 同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即 为求无向网的最小生成树。2）要求：在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资 最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。3）测试数据: 使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参 考解。4）输入输出:完整代码：#includeiostream #includestdlib
2、.h #defineMAX_VERTEX_NUM20 typedeffloatWeightType; typedefstructArcNodeintadjvex;WeightTypeweight; structArcNode*nextarc;ArcNode; typedefstructVertexNodechardata;ArcNode*firstarc;VertexNode,AdjListMAX_VERTEX_NUM; typedefstructAdjListvertices;intvexnum,arcnum;intkind;ALGraph; intLocateVex(ALGraphG,ch
3、arv) inti;for(i=0;iG.vexnum;i+)if(G.verticesi.data=v)returni;voidCreateGraph(ALGraph&G)inti,j,k;charvi,vj;WeightTypeweight;ArcNode*p,*q;std:coutG.vexnumG.arcnumG.kind;for(i=0;iG.vexnum;i+)std:coutG.verticesi.data;G.verticesi.firstarc=NULL;for(k=0;kG.arcnum;k+)std:coutvivjweight;i=LocateVex(G,vi);j=L
4、ocateVex(G,vj); p=(ArcNode*)malloc(sizeof(ArcNode); p-adjvex=j;p-weight=weight;p-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p;if(G.kind=2)q=(ArcNode*)malloc(sizeof(ArcNode);q-adjvex=i;q-weight=p-weight;q-nextarc=G.verticesj.firstarc;G.verticesj.firstarc=q;intMinEdge(WeightTypelowcost,intvexmu
5、n)inti,k;WeightTypej;k=0;while(lowcostk=0)k+;j=lowcostk;for(i=k+1;ivexmun;i+)if(lowcosti!=0&lowcostij)j=lowcosti;k=i; voidPrim(ALGraphG,intv0,intadjvex)WeightTypelowcostMAX_VERTEX_NUM; inti,k;ArcNode*p;for(i=0;iadjvex=p-weight;p=p-nextarc;lowcostv0=0;for(i=0;i=G.vexnum) std:cout(k,adjvexk),lowcostkweightadjvex)adjvexp-adjvex=k;lowcostp-adjvex=p-weight;p=p-nextarc;intmain()intadjvexMAX_VERTEX_NUM;ALGraphG;G.kind=2;CreateGraph(G);Prim(G,0,adjvex);return0;/*测试数据9152ABDEFGHIAB32.8AI18.2AH12.1AC44.6BC5.9CD21.3CE41.1CG56.4DE67.3DF98.7EF85.6EG10.5HG52.5IH8.7IF79.2*/
管道铺设施工的最佳方案
