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

1）内容：需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。2）要求：在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。3)测试数据:使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。4）输入输出:参考完整代码：#includeiostream#includestdlib.h#defineMAX_VERTEX_NUM20typedeffloatWeightType;typedefstructArcNode{intadjvex;WeightTypeweight;structArcNode*nextarc;}ArcNode;typedefstructVertexNode{chardata;ArcNode*firstarc;}VertexNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;intLocateVex(ALGraphG,charv){inti;for(i=0;iG.vexnum;i++){if(G.vertices[i].data==v)returni;}return-1;}voidCreateGraph(ALGraph&G){inti,j,k;charvi,vj;WeightTypeweight;ArcNode*p,*q;std::cout请输入顶点个数，边数和图的类型：\n;std::cinG.vexnumG.arcnumG.kind;for(i=0;iG.vexnum;i++){std::cout请输入各个顶点：\n;std::cinG.vertices[i].data;G.vertices[i].firstarc=NULL;}for(k=0;kG.arcnum;k++){std::cout请输入两顶点和其边的权值：\n;std::cinvivjweight;i=LocateVex(G,vi);j=LocateVex(G,vj);p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-weight=weight;p-nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;if(G.kind==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){k++;}j=lowcost[k];for(i=k+1;ivexmun;i++){if(lowcost[i]!=0&&lowcost[i]j){j=lowcost[i];k=i;}}returnk;}voidPrim(ALGraphG,intv0,intadjvex[]){WeightTypelowcost[MAX_VERTEX_NUM];inti,k;ArcNode*p;for(i=0;iG.vexnum;i++){if(i!=v0){lowcost[i]=999;adjvex[i]=v0;}}p=G.vertices[v0].firstarc;while(p){lowcost[G,p-adjvex]=p-weight;p=p-nextarc;}lowcost[v0]=0;for(i=0;iG.vexnum;i++){k=MinEdge(lowcost,G.vexnum);if(k=G.vexnum)return;std::cout(k,adjvex[k]),lowcost[k]'\n';lowcost[k]=0;p=G.vertices[k].firstarc;while(p){if(p-weightlowcost[p-adjvex]){adjvex[p-adjvex]=k;lowcost[p-adjvex]=p-weight;}p=p-nextarc;}}}intmain(){intadjvex[MAX_VERTEX_NUM];ALGraphG;G.kind=2;CreateGraph(G);Prim(G,0,adjvex);return0;}/*测试数据9152ABCDEFGHIAB32.8AI18.2AH12.1AC44.6BC5.9CD21.3CE41.1CG56.4DE67.3DF98.7EF85.6EG10.5HG52.5IH8.7IF79.2*/