管道铺设施工的最佳方案完整程序代码

《管道铺设施工的最佳方案完整程序代码》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1）内容：需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设旷1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理坏境不同,所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。2）要求：在可能假设的m条管道屮，选収「1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网笊存储采用邻接表的结构。3）测试数据：使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。4）输入输出：参考完整代码：#include"iostream"#include"s

2、tdlib.h"#defineMAX_VERTEX_NUM20typedeffloatWeightType;typedefstructArcNode{intadjvex;WeightTypeweight;structArcNode*nextarc;JArcNode;typedefstructVertexNode{chardata;ArcNode*firstarc;}VertexNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;intLocat

3、eVexfALGraphG,charv){inti;for(i=0;i

4、»G.vertices[i].data;G.vertices[i].firstarc=NULL;}for(k=0;kadjvex=j;p->weight=weight;p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;if(G.kin

5、d==2)q=(ArcNode*)malloc(sizeof(ArcNode));q->adjvex=i;q->weight=p->weight;q・>nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=q;intMinEdge(WeightTypelowcost[],intvexmun){inti,k;WeightTypej;k=0;while(lowcost[k]==0)j=lowcost[k];for(i=k+1;i

6、ost[i];k=i;}returnk;}voidPrim(ALGraphG,intvO,intadjvex[])WeightTypelowcost[MAX_VERTEX_NUM];inti,k;ArcNode*p;for(j=0;iadjvex]=p->weight;p=p->nextarc;}Iowcost[v0]=0;for(i=0;i

7、dgeflowcost,G.vexnum);if(k>=G.vexnum)return;std::cout«"("«k««adjvex[k]««lowcost[k]«'';lowcost[k]=0;p=G.vertices[k].firstarc;while(p){if(p->weightadjvex]){adjvex[p->adjvex]=k;lowcost[p->adjvex]=p->weight;}p=p・>nextarc;}}}intmain(){intadjve刈M