實(shí)驗(yàn)三：管道鋪設(shè)施工的最佳方案

實(shí)驗(yàn)三：管道鋪設(shè)施工的最佳方案

一.問(wèn)題描述

1.實(shí)驗(yàn)題目：

需要在某個(gè)城市n個(gè)居民小區(qū)之間鋪設(shè)煤氣管道，則在這n個(gè)居民小區(qū)之間只需要鋪設(shè)n-1

條管道鋪設(shè)n-1條管道即可。假設(shè)任意兩個(gè)小區(qū)之間則可以鋪設(shè)管道，但由于地理環(huán)境不同，

所需要的費(fèi)用也不盡相同。選擇最優(yōu)的方案能使總投資盡可能小，這個(gè)問(wèn)題即為求無(wú)向網(wǎng)的

最小生成樹(shù)。

2.基本要求：

在可能假設(shè)的m條管道中，選取n-1條管道，使得既能連通n個(gè)小區(qū)，又能使總投資最小。

每條管道的費(fèi)用以網(wǎng)中該邊的權(quán)值形式給出，網(wǎng)的存儲(chǔ)采用鄰接表的結(jié)構(gòu)。

3.測(cè)試數(shù)據(jù)：

使用下圖給出的無(wú)線網(wǎng)數(shù)據(jù)作為程序的輸入，求出最佳鋪設(shè)方案。

98.7

參考解:

二.需求分析

1.程序所能達(dá)到的基本可能：

在某個(gè)城市n個(gè)居民小區(qū)之間鋪設(shè)煤氣管道，則在這n個(gè)居民小區(qū)之間只需要鋪設(shè)n-1條管

道鋪設(shè)n-1條管道即可。假設(shè)任意兩個(gè)小區(qū)之間則可以鋪設(shè)管道，但由于地理環(huán)境不同，所

需要的費(fèi)用也不盡相同。選擇最優(yōu)的方案能使總投資盡可能小，在可能假設(shè)的m條管道中，

選取n-1條管道，使得既能連通n個(gè)小區(qū)，又能使總投資最小。

2.輸入輸出形式及輸入值范圍：程序運(yùn)行后，顯示提示信息：請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)（輸入格

式為：頂點(diǎn)數(shù)，邊數(shù)）之后程序從文件名為“C:\Vlata.txt讀入頂點(diǎn)信息和邊的信息，之后

顯示提示信息輸入開(kāi)始節(jié)點(diǎn)，執(zhí)行生成最小樹(shù)程序，輸出生成的最小樹(shù)信息。

3.測(cè)試數(shù)據(jù)要求：頂點(diǎn)數(shù)邊數(shù)為整數(shù)，頂點(diǎn)信息為大寫(xiě)字母，邊的權(quán)值為浮點(diǎn)型，

C:\\data.txt文件內(nèi)容為:ABCDEFGHI

1232.8235.91344.63421.34567.34698.75685.65710.53756.46

979.27852.51812.1898.71918.23541.1

三.概要設(shè)計(jì)

1.所用到得數(shù)據(jù)結(jié)構(gòu)及其ADT

typedefstructnode〃邊表結(jié)點(diǎn)

intNO;〃鄰接點(diǎn)域;

vertexTypeadjvex;

EdgeTypeinfo;〃權(quán)值

structnode*next;〃指向下一個(gè)鄰接點(diǎn)的指針域

}EdgeNode;

typedefstructvnode〃頂點(diǎn)表節(jié)點(diǎn)

(

vertexTypevertex;〃頂點(diǎn)域

EdgeNode*firstedge;〃編表頭指針

}VertexNode;

typedefstruct〃鄰接表

VertexNodeadjlist[MaxVertexNum];

intn,e;〃頂點(diǎn)數(shù)和邊數(shù)

}ALGraph;//ALGraph是以鄰接表方式存儲(chǔ)的圖類(lèi)型

基本操作：ALGraph*CreateALGraphO〃建表

2.主程序流程及其模塊調(diào)用關(guān)系

建表模塊ALGraph*CreateALGraph()

最小生成樹(shù)模塊voidtree(ALGraph*G,intm)

函數(shù)調(diào)用關(guān)系圖

四、詳細(xì)設(shè)計(jì)

1.實(shí)現(xiàn)每個(gè)操作的偽碼，重點(diǎn)語(yǔ)句加注釋

1)建表模塊

ALGraph*CreateALGraph()〃建表

!

inti,j,k;

floatm;

FILE*fp;

EdgeNode*s,*t;

ALGraph*G;

fp=fopenCC:\\data.txt",〃r");〃打開(kāi)文件

if(fp=NULL)〃未找到文件

(

printf(，，Cann，topenthefile!\n");

exit(1);

)

G=(ALGraph*)malloc(sizeof(ALGraph));

printf(〃請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為：頂點(diǎn)數(shù)，邊數(shù))\n〃)；

scanf(〃%d,%d〃,&G->n,&G->e);

for(i=l;i<=G->n;i++)〃建立頂點(diǎn)信息

(

G->adjlist[i].vertex=fgetc(fp);

G->adjlist[i].firstedge=NULL;

visited[i]=i;

}

for(k=l;k<=G->e;k++)

(

//printf(〃請(qǐng)輸入第%d條邊的兩個(gè)端點(diǎn)序號(hào)，輸入格式為：i,八n〃,k);

//scanf(〃％d,%d〃,&i,&j);

fscanf(fp,〃％d〃，&i);

fscanf(fp,"%d",&j);

s=(EdgeNode*)malloc(sizeof(EdgeNode));

t=(EdgeNode*)malloc(sizeof(EdgeNode));

//printf(〃請(qǐng)輸入第加條邊的對(duì)應(yīng)權(quán)值\n〃,k);

fscanf;〃保存邊信息，以無(wú)向網(wǎng)方式

s->NO=j;

s->adjvex=G->adj1ist[j].vertex;

s->info=m;

s->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=s;

t->N0=i;

t->adjvex=G->adjlist[i].vertex;

t->info=m;

t->next=G->adjlist[j].firstedge;

G->adjlist[j].firstedge=t;

)

fclose(fp);〃關(guān)閉文件

returnG;

)

2)生成最小生成樹(shù)模塊

voidtree(ALGraph*G,intm)

I

floatlow[100];intteed[100];

intk,i,j;

floatmin,sum=0;

EdgeNode*s;

low[m]=0;

visited[m]=0;

for(i=l;i<=G->n;i++)

(

low[i]=1000;

teed[i]=m;

}

s=G->adjlist[m].firstedge;

while(s!=NULL)〃數(shù)組初始化

(

low[s->N0]=s->info;

s=s->next;

)

for(i=l;i<G->n;i++)

min=1000;

for(j=l;j<=G->n;j++)

if(visited[j]>0&&low[jkmin)〃找到最小權(quán)值

min=low[j];

k=j;〃標(biāo)記節(jié)點(diǎn)

)

}

sum+=min;

visited[k]=O;

s=G->adjlist[k].firstedge;

while(s!=NULL)

(

if(visited[s->N0]>0&&s->info〈low[s->N0])〃找到最小權(quán)值

(

low[s->NO]=s->info;

teed[s->N0]=k;

)

s=s->next;

)

}

printf(〃最佳鋪設(shè)方案\n〃)；

for(i=l;i<=G->n;i++)〃輸出最小生成樹(shù)信息

if(i!=m)

printfC，(%d,%d)%.2f\t，z,i,teed[i],low[i]);

printf(〃最小權(quán)值為:％.2f\n〃，sum);

)

3)主函數(shù)模塊

voidmain()

!

ALGraph*G;

inti;

timetrawtime;

structtm*timeinfo;

time(&rawtime);

timeinfo=localtime(ftrawtime);

printfC實(shí)驗(yàn)名稱(chēng)：實(shí)驗(yàn)三：管道鋪設(shè)施工的最佳方案\n");

printf(，z學(xué)號(hào)：031350102\nz，);

printfC姓名：王亞文\n〃)；

printf；

printf(〃程序運(yùn)行開(kāi)始，〃)；

printf(，zCurrentlocaltimeanddate:%sz\asctime(timeinfo));

G=CreateALGraph();〃建表

printf(〃輸入開(kāi)始節(jié)點(diǎn)\n〃);

scanf("%d",&i);

tree(G,i);〃生成最小樹(shù)

//printfALGraph(G);

printf(〃\n〃)；

printf("'Currentlocaltimeanddate^s^,asctime(timeinfo));

)

五、調(diào)試分析

1.設(shè)計(jì)與調(diào)試過(guò)程中遇到的問(wèn)題分析、體會(huì)

1)一開(kāi)始對(duì)文件讀寫(xiě)操作不熟，采用從鍵盤(pán)輸出的方式驗(yàn)證正確與否，對(duì)應(yīng)程序如下:

inti,j,k;

floatm;

EdgeNode*s,*t;

ALGraph*G;

G=(ALGraph*)malloc(sizeof(ALGraph));

printf(〃請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為：頂點(diǎn)數(shù)，邊數(shù))\n〃)；

scanf("%d,%d〃，&G->n,&G->e);

for(i=l;i<=G->n;i++)〃建立頂點(diǎn)信息

G->adjlist[i].vertex=fgetc(fp);

G->adjlist[i].firstedge=NULL;

visited[i]=i;

i

for(k=l;k<=G->e;k++)

(

printf(〃請(qǐng)輸入第%d條邊的兩個(gè)端點(diǎn)序號(hào)，輸入格式為：i,j\n〃,k);

scanf(〃％d,%d〃,&i,&j);

s=(EdgeNode*)malloc(sizeof(EdgeNode));

t=(EdgeNode*)malloc(sizeof(EdgeNode));

printf(〃請(qǐng)輸入第%d條邊的對(duì)應(yīng)權(quán)值\n〃,k);

scanfr%fzz,&m);〃保存邊信息，以無(wú)向網(wǎng)方式

s->N0=j;

s->adjvex=G->adjlist[j].vertex;

s->inform;

s->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=s;

t->N0=i;

t->adjvex=G->adjlist[i].vertex;

t->info=m;

t->next=G->adjlist[j].firstedge;

G->adjlist[j].firstedge=t;

}

returnG;

對(duì)應(yīng)截屏如下：發(fā)現(xiàn)這種方式輸入耗時(shí)長(zhǎng)，而且在生成樹(shù)程序不正確時(shí)修改程序需要重復(fù)輸

入，較為麻煩

-

睛輸入第7條邊的對(duì)應(yīng)權(quán)值

85.6

請(qǐng)輸入第8條邊的兩個(gè)端點(diǎn)序號(hào)，輸入格式為：

5,7

請(qǐng)輸入第8條邊的對(duì)應(yīng)權(quán)值

10.5

請(qǐng)輸入第9條邊的兩個(gè)端點(diǎn)序號(hào)，輸入格式為：

37

宿輸入第9條邊的對(duì)應(yīng)權(quán)值

56.4

請(qǐng)輸入第［。條邊的兩個(gè)端點(diǎn)序號(hào)，輸入格式為：

德輸入第條邊的對(duì)應(yīng)權(quán)值

79.2

請(qǐng)輸入第11條邊的兩個(gè)端點(diǎn)序號(hào),輸入格式為：

78

港輸入第11條邊的對(duì)應(yīng)權(quán)值

52.5

請(qǐng)輸入第12條邊的兩個(gè)端點(diǎn)序號(hào),輸入格式為：

1,8

請(qǐng)輸入第12條邊的對(duì)應(yīng)權(quán)值

12.1

請(qǐng)輸入第13條邊的兩個(gè)端點(diǎn)序號(hào),輸入格式為：i，j

褊｝入第13條邊的對(duì)應(yīng)權(quán)值

8.?

請(qǐng)輸入第14條邊的兩個(gè)端點(diǎn)序號(hào),輸入格式為：i，J

善徐入第14條邊的時(shí)應(yīng)權(quán)值

182

請(qǐng)輸入第15條邊的兩個(gè)端點(diǎn)序號(hào),輸入格式為：i，j

3,5

請(qǐng)輸入第15條邊的對(duì)應(yīng)權(quán)值

41.1

輸入開(kāi)始節(jié)點(diǎn)

1

<2,1>32.80<3,2>5.90<4,3>21.30<5,3>41.10<6,9>79.20

<7,5>10.50<8,1>12.10<9,8>8.70輸出信息

A的鄰接點(diǎn)及權(quán)值;

h18.20H12.10C44.60B32.80

B的鄰接點(diǎn)及權(quán)值:

5.90A32.80

的鄰接點(diǎn)及權(quán)值B!:

C的鄰接點(diǎn)及權(quán)值：

E41.10G56.40D21.30A44.60B5.90

D的鄰接點(diǎn)及權(quán)值：

F98.70E67.30C21.30

E的鄰接點(diǎn)及權(quán)值：

C41.10G10.50F85.60D67.30

F的鄰接點(diǎn)及權(quán)值：

I79.20E85.60D98.70

G的鄰接點(diǎn)及權(quán)值：

H52.50C56.4010.50

H的鄰接點(diǎn)及權(quán)值：

I8.70A12.10G52.50

I的鄰接點(diǎn)及權(quán)值：

h18.20H8.7079.20

pressanykeytocontinue

2)為檢驗(yàn)所建立的無(wú)向網(wǎng)，編寫(xiě)了一個(gè)輸出函數(shù)，輸出各個(gè)頂點(diǎn)以及與該頂點(diǎn)相鄰的其他

頂點(diǎn)以及對(duì)應(yīng)權(quán)值，輸出函數(shù)為voidprintfALGraph(ALGraph*G)〃輸出表

inti;

EdgeNode*s;

printf("輸出信息\n");

for(i=l;i<=G->n;i++)

(

printf(z，%c的鄰接點(diǎn)及權(quán)值:\n〃,G->adjlist[i].vertex);

s=G->adjlist[i].firstedge;

while(s!=NULL)

(

printf(，z%c%.2f”,s->adjvex,s->info);

s=s->next;

)

printf(〃\n〃)；

}

輸出測(cè)試截屏如下證明從文件讀寫(xiě)的與所需要建立的無(wú)向網(wǎng)相符

|l?C:\USERS\ADMINISTRATOR\DESKTOP\VC\Debug\sa.exe,--X

窈驗(yàn)名稱(chēng)：實(shí)驗(yàn)三：管道鋪設(shè)施工的最佳方案

學(xué)號(hào)：031350102

姓名：王亞文

行呈序運(yùn)彳丁開(kāi)始，Currentlocaltimeanddate：ThuNou1215:29:122015

情輸入頂點(diǎn)數(shù)和邊數(shù)（輸入格式為:頂點(diǎn)數(shù)，邊數(shù)）

9,15

輸入開(kāi)始節(jié)點(diǎn)

1

<9,8>8.70<2,1>32.80<3,2>5.90<4,3>21.30<5,3>41.10

<6,9）79.20<7,5>10.50<8,1>12.10<9,8>8.70輸出信息

A的鄰接點(diǎn)及權(quán)值:

I18.20H12.1044.60B32.80

B的鄰接點(diǎn)及權(quán)值：

C5.90A32.80

C的鄰接點(diǎn)及權(quán)值：

E41.10G56.4021.30A44.60B5.90

D的鄰接點(diǎn)及權(quán)值：

F98.70E67.3021.30

E的鄰接點(diǎn)及權(quán)值：

C41.10G10.50F85.6067.30

F的鄰接點(diǎn)及權(quán)值：

I79.20E85.60D98.70

G的鄰接點(diǎn)及權(quán)值：

H52.5056.4010.50

H的鄰接點(diǎn)及權(quán)值：

I8.?0A12.10

I的鄰接點(diǎn)及權(quán)值：

A18.20H8.70F79.20

(Currentlocaltineanddate：ThuNou1215:29:122015

Pressanykeytocontinue

2.主要算法的時(shí)間復(fù)雜度分析

六、使用說(shuō)明

程序運(yùn)行后，顯示提示信息：請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)（輸入格式為：頂點(diǎn)數(shù)，邊數(shù)）之后程序

從文件名為"C:\\data.txt讀入頂點(diǎn)信息和邊的信息，之后顯示提示信息輸入開(kāi)始節(jié)點(diǎn)，

執(zhí)行生成最小樹(shù)程序，輸出生成的最小樹(shù)信息。

七、測(cè)試結(jié)果

|D：回漢

■'C:\USERS\ADMINISTRATOR\DESKTOP\VC\Debug\sa.exe'

需驗(yàn)名稱(chēng)：實(shí)驗(yàn)三：管道鋪設(shè)施工的最佳方案

學(xué)號(hào)：031350102

姓名：王亞文

程序達(dá)彳丁開(kāi)始，Currentlocaltimeanddate：ThuNou1215：33：442015

請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)（輸入格式為：頂點(diǎn)數(shù)，邊數(shù)）

輸入開(kāi)始節(jié)點(diǎn)

￡佳鋪設(shè)方案

<2,1>32.80<3,2>5.90<4,3>21.30<5,3>41.10<6,9>79.20

<7,5>10.50<8,1>12.10<9,8>8.?0最小權(quán)值為：211.60

Currentlocaltineanddate：ThuNou1215：33：442015

Pressanykeytocontinue

3）這個(gè)程序遇到的第一個(gè)主要問(wèn)題是在建表過(guò)程，因?yàn)檫叺捻旤c(diǎn)信息是大寫(xiě)英文字母，一

開(kāi)始我是用的ASCLL碼值，使用不方便，后來(lái)采用在定義時(shí)考慮多定義一個(gè)量，原程序：

typedefstructnode〃邊表結(jié)點(diǎn)

j

vertexTypeadjvex;〃鄰接點(diǎn)域；

EdgeTypeinfo;〃權(quán)值

structnode*next;〃指向下一個(gè)鄰接點(diǎn)的指針域

}EdgeNode;

修正后的程序?yàn)?

typedefstructnode〃邊表結(jié)點(diǎn)

t,1

intNO;〃鄰接點(diǎn)域；

vertexTypeadjvex;

EdgeTypeinfo;〃權(quán)值

structnode*next;〃指向下一個(gè)鄰接點(diǎn)的指針域

}EdgeNode;

這樣多定義了一個(gè)量在后面的過(guò)程中會(huì)簡(jiǎn)單許多，其次書(shū)上給的程序是生成有向網(wǎng)的，

開(kāi)始我是考慮的將邊輸入兩邊，就是在循環(huán)時(shí)的終止條件設(shè)為k?2*G-〉6；這樣雖然能解決

無(wú)向網(wǎng)問(wèn)題，但是一條邊重復(fù)輸入兩邊，較為麻煩，后期修正為：

s->NO=j;

s->adjvex=G->adjlist[j].vertex;

s->info=m;

s->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=s;

t->NO=i;

t->adjvex=G->adjlist[i].vertex;

t->info=m;

t->next=G->adjlist[j].firstedge;

G->adjlist[j].firstedge=t;

修正后的函數(shù)雖然語(yǔ)句較之前的多了5句但在輸入時(shí)少輸了一半的邊信息。其次解決耗時(shí)最

長(zhǎng)的一個(gè)錯(cuò)誤是在建表中，原程序：

typedefVertexNodeAdjlist[MaxVertexNum];

typedefstruct〃鄰接表

{

Adjlistadjlist;

//intn,e;〃頂點(diǎn)數(shù)和邊數(shù)

intn;

inte;

}ALGraph;//ALGraph是以鄰接表方式存儲(chǔ)的圖類(lèi)型

這個(gè)程序是抄的書(shū)上的，一開(kāi)始不覺(jué)得書(shū)上的程序會(huì)是錯(cuò)的，結(jié)果一直沒(méi)有看這個(gè)定義，在

輸入邊的信息時(shí)循環(huán)次數(shù)總是不對(duì)，一直嘗試著改動(dòng)寫(xiě)的輸入信息，弄了一下午也沒(méi)有搞定

這個(gè)問(wèn)題，于是去求助研究生學(xué)長(zhǎng)，下面是研究生學(xué)長(zhǎng)發(fā)過(guò)來(lái)的郵件幫我指出錯(cuò)誤所在，看

了學(xué)長(zhǎng)的這封郵件后，重新改了一下自己的程序，修正后的程序?yàn)?/p>

typedefstruct〃鄰接表

!

VertexNodeadjlist[MaxVertexNum];

intn,e;〃頂點(diǎn)數(shù)和邊數(shù)

}ALGraph;//ALGraph是以鄰接表方式存儲(chǔ)的圖類(lèi)型

問(wèn)題所在:結(jié)構(gòu)體ALGraph(紅色標(biāo)記部分)中，"Adjlistadjlistf語(yǔ)句定義錯(cuò)誤，上

面沒(méi)有定義Adjlist這個(gè)類(lèi)型；|

解決方案：考慮在主函數(shù)main()中將全局結(jié)構(gòu)體數(shù)組typedefVertexNode

AdjlistfMaxVertexNum];中Adjlist數(shù)組名作為參數(shù)進(jìn)入ALGraph*

CreateALGraph()

即ALGraph*CreateALGraph(VertexNode*adjlist);

將的訪問(wèn)方式更改為原因:該結(jié)構(gòu)體數(shù)組定義為全局結(jié)構(gòu)體

G->adjliSt[i].xadjlist[i].x,

數(shù)組無(wú)須通過(guò)ALGraph結(jié)構(gòu)體指針G來(lái)訪同使用數(shù)組指針VertexNode*adjlist方便

快捷

程序修正后輸入正常了，就開(kāi)始進(jìn)入下一個(gè)階段生成最小樹(shù)的程序。

3)在生成最小樹(shù)這個(gè)程序的編寫(xiě)中，開(kāi)始因?yàn)榫幊绦蚴窃诶蠋熤v解生成樹(shù)之前，所以一開(kāi)

始是完全沒(méi)有地方下手，網(wǎng)上百度了一下如何生成最小樹(shù)，發(fā)現(xiàn)有兩種方法,Kruskal和prim

算法，但研究生學(xué)長(zhǎng)這個(gè)適合用prim算法，Kruskal算法適合與邊稀疏的連通圖求解最小

生成樹(shù)，所以在編寫(xiě)時(shí)主要研究的是用prim算法，在編寫(xiě)prim算法時(shí)除了很多問(wèn)題，例如

一開(kāi)始我并沒(méi)有在循環(huán)中寫(xiě)teed[i]=m;這句話，導(dǎo)致在最后輸出邊的信息時(shí)會(huì)有隨機(jī)數(shù)產(chǎn)

生，截圖如下：

最佳鋪設(shè)方案

(2,-858993460>32.80<3,2>5.90<4,3>21.30<5,3>41.10<6,9>79.

20<8,-858993460>12.10<9,8>8,70最小權(quán)值為

想到隨機(jī)數(shù)產(chǎn)生可能是因?yàn)闆](méi)有賦值，所以加上teed[i]=m;這句話果然最后就輸出正確了，

再次在輸出時(shí)，產(chǎn)生的結(jié)果中有重復(fù)的一個(gè)節(jié)點(diǎn)，<1,D1000.00這個(gè)不應(yīng)該被輸出，所以

考慮在輸出時(shí)加一個(gè)限制條件if(i!=m)再次輸出就沒(méi)有了，

最佳鋪設(shè)方案

<1,1>1000.00<2,1>32.80<3,2>5.90<4,3>21.30<5,3>41.10

<6,9>79.20<7,5>10.50<8,1>12.10<9,8>8.70最小權(quán)值為

0

中間編寫(xiě)時(shí)問(wèn)題不大，之前有看過(guò)prim算法的詳細(xì)介紹，所以在主思路上沒(méi)有太大的錯(cuò)誤,

相對(duì)寫(xiě)起來(lái)也比較順利。

2)建立鄰接表的復(fù)雜度為0(n+e);

Prim算法的時(shí)間復(fù)雜度為O(elogn);

八、附錄

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

#include<time.h>

〃輸入序號(hào)與字母對(duì)應(yīng)關(guān)系A(chǔ)T,,B-2,C-3,D-4,E-5,F-6,G-7,H-8,1-9

#defineMaxVertexNum100

typedefcharvertexType;

typedeffloatEdgeType;

intvisited[100];〃訪問(wèn)變量,為一時(shí)表示未訪問(wèn)

typedefstructnode〃邊表結(jié)點(diǎn)

f

intNO;〃鄰接點(diǎn)域；

vertexTypeadjvex;

EdgeTypeinfo;〃權(quán)值

structnode*next;〃指向下一個(gè)鄰接點(diǎn)的指針域

}EdgeNode;

typedefstructvnode〃頂點(diǎn)表節(jié)點(diǎn)

if

vertexTypevertex;〃頂點(diǎn)域

EdgeNode*firstedge;〃編表頭指針

}VertexNode;

typedefstruct〃鄰接表

VertexNodeadjlist[MaxVertexNum];

intn,e;〃頂點(diǎn)數(shù)和邊數(shù)

}ALGraph;//ALGraph是以鄰接表方式存儲(chǔ)的圖類(lèi)型

ALGraph*CreateALGraph()〃建表

inti,j,k;

floatm;

FILE*fp;

EdgeNode*s,*t;

ALGraph*G;

fp=fopenCC:\\data.txt","r");〃打開(kāi)文件

if(fp=NULL)〃未找到文件

(

printf("Carin'topenthefile!\n〃)；

exit(1);

}

G=(ALGraph*)malloc(sizeof(ALGraph));

printf(〃請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為：頂點(diǎn)數(shù)，邊數(shù))\n〃)；

scanf(〃%d,%d”,&G->n,&G->e);

for(i=l;i<=G->n;i++)〃建立頂點(diǎn)信息

(

G->adjlist[i].vertex=fgetc(fp);

G->adjlist[i].firstedge=NULL;

visited[i]=i;

1

for(k=l;k<=G->e;k++)

(

//printf(〃請(qǐng)輸入第%(1條邊的兩個(gè)端點(diǎn)序號(hào)，輸入格式為：i,j\n〃,k);

//scanfC%d,%d",&i,&j);

fscanf(fp,〃%d〃，&i);

fscanf(fp,〃％d〃，&j);

s=(EdgeNode*)malloc(sizeof(EdgeNode));

t=(EdgeNode*)malloc(sizeof(EdgeNode));

//printf(〃請(qǐng)輸入第%d條邊的對(duì)應(yīng)權(quán)值\n〃,k);

fscanf(fp,〃%f”,&m);〃保存邊信息，以無(wú)向網(wǎng)方式

s->NO=j;

s->adjvex=G->adjlist[j].vertex;

s->info=m;

s->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=s;

t->NO=i;

t->adjvex=G->adjlist[i].vertex;

t->info=m;

t->next=G->adjlist[j].firstedge;

G->adjlist[j].firstedge=t;

)

fclose(fp);〃關(guān)閉文件

returnG;

)

voidtree(ALGraph*G,intm)

!

floatlow[100];intteed[100];

intk,i,j；

floatmin,sum=0;

EdgeNode*s;

low[m]=0;

visited[m]=0;

for(i=l;i<=G->n;i++)

low[i]=1000;

teed[i]=m;

}

s=G->adjlist[m].firstedge;

while(s!=NULL)〃數(shù)組初始化

low[s->NO]=s->info;

s=s->next;

}

for(i=l;i<G->n;i++)

(

min=1000;

for(j=l;j<=G->n;j++)

(

if(visit6d[j]〉0&&low[j]〈min)〃找到最小權(quán)值

(

min=low[j];

k=j;〃標(biāo)記節(jié)點(diǎn)

)

}

sum+二min;

visited[k]=O;

s=G->adjlist[kJ.firstedge;

while(s!=NULL)

(

if(visited[s->N0]>0&&s->info<low[s->N0])〃找到最小權(quán)值

(

low[s->NO]=s->info;

teed[s->N0]zzk;

}

s=s->next;

)

)

printf（〃最佳鋪設(shè)方案\n〃）;

for(i=l;i〈=G->n;i++)〃輸出最小生成樹(shù)信息

if(i!=m)

printf(〃(%d,%d)%.2f\t，z,i,teed[i],low[i]);

printf(〃最小權(quán)值為:%.2f\n〃，sum);

)

AvoidprintfALGraph(ALGraph*G)〃輸出表

{

inti;

EdgeNode*s;

printf(〃輸出信息信");

for(i=l;i<=G->n;i++)

(

printfCz%c的鄰接點(diǎn)及權(quán)值：\n”,G->adjlist[i].vertex);

s=G->adjlist[i].firstedge;

while(s!=NULL)

(

printf(z，%c%.2f:s->adjvex,s->in