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

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

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

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<

G.vexnum;

i++）

{

if（G.vertices[i].data==v）

returni;

}

return-1;

}

voidCreateGraph（ALGraph&

G）

inti,j,k;

charvi,vj;

ArcNode*p,*q;

std:

:

cout<

<

"

请输入顶点个数，边数和图的类型：

\n"

;

cin>

>

G.vexnum>

G.arcnum>

G.kind;

for（i=0;

std:

请输入各个顶点：

G.vertices[i].data;

G.vertices[i].firstarc=NULL;

for（k=0;

k<

G.arcnum;

k++）

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

vi>

vj>

weight;

i=LocateVex（G,vi）;

j=LocateVex（G,vj）;

p=（ArcNode*）malloc（sizeof（ArcNode））;

p->

adjvex=j;

weight=weight;

nextarc=G.vertices[i].firstarc;

G.vertices[i].firstarc=p;

if（G.kind==2）

{

q=（ArcNode*）malloc（sizeof（ArcNode））;

q->

adjvex=i;

weight=p->

weight;

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;

vexmun;

if（lowcost[i]!

=0&

&

lowcost[i]<

j）

j=lowcost[i];

k=i;

returnk;

voidPrim（ALGraphG,intv0,intadjvex[]）

WeightTypelowcost[MAX_VERTEX_NUM];

ArcNode*p;

if（i!

=v0）

lowcost[i]=999;

adjvex[i]=v0;

p=G.vertices[v0].firstarc;

while（p）

lowcost[G,p->

adjvex]=p->

p=p->

nextarc;

lowcost[v0]=0;

k=MinEdge（lowcost,G.vexnum）;

if（k>

=G.vexnum）

return;

（"

<

"

adjvex[k]<

）,"

lowcost[k]<

'

\n'

lowcost[k]=0;

p=G.vertices[k].firstarc;

while（p）

if（p->

weight<

lowcost[p->

adjvex]）

{

adjvex[p->

adjvex]=k;

lowcost[p->

}

p=p->

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

*/

页脚内容