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

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

《管道铺设施工的最佳方案 完整程序代码.docx》由会员分享，可在线阅读，更多相关《管道铺设施工的最佳方案 完整程序代码.docx（7页珍藏版）》请在冰点文库上搜索。

管道过河工程施工方案

1）内容：

需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道即可。

假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。

选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。

2）要求：

在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。

每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。

3）测试数据:

使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。

右侧是给出的参考解。

4）输入输出:

参考

完整代码：

#include"iostream"

#include"stdlib.h"

#defineMAX_VERTEX_NUM20

typedeffloatWeightType;

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;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:

:

cin>>G.vexnum>>G.arcnum>>G.kind;

for（i=0;i

{

std:

:

cout<<"请输入各个顶点：

\n";

std:

:

cin>>G.vertices[i].data;

G.vertices[i].firstarc=NULL;

}

for（k=0;k

{

std:

:

cout<<"请输入两顶点和其边的权值：

\n";

std:

:

cin>>vi>>vj>>weight;

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;i

{

if（lowcost[i]!

=0&&lowcost[i]

{

j=lowcost[i];

k=i;

}

}

returnk;

}

voidPrim（ALGraphG,intv0,intadjvex[]）

{

WeightTypelowcost[MAX_VERTEX_NUM];

inti,k;

ArcNode*p;

for（i=0;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;i

{

k=MinEdge（lowcost,G.vexnum）;

if（k>=G.vexnum）

return;

std:

:

cout<<"（"<

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（）

{

intadjvex[MAX_VERTEX_NUM];

ALGraphG;

G.kind=2;

CreateGraph（G）;

Prim（G,0,adjvex）;

return0;

}

/*测试数据

9152

A

B

C

D

E

F

G

H

I

AB32.8

AI18.2

AH12.1

AC44.6

BC5.9

CD21.3

CE41.1

CG56.4

DE67.3

DF98.7

EF85.6

EG10.5

HG52.5

IH8.7

IF79.2

*/

页脚内容