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

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

一.問題描述

1.實驗題目：

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

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

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

最小生成樹。

2.基本要求：

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

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

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

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

98.7

參考解:

二.需求分析

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

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

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

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

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

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

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

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

3.測試數(shù)據(jù)要求：頂點(diǎn)數(shù)邊數(shù)為整數(shù)，頂點(diǎn)信息為大寫字母，邊的權(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è)計

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

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

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

vertexTypeadjvex;

EdgeTypeinfo;〃權(quán)值

structnode*next;〃指向下一個鄰接點(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是以鄰接表方式存儲的圖類型

基本操作：ALGraph*CreateALGraphO〃建表

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

建表模塊ALGraph*CreateALGraph()

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

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

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

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

1)建表模塊

ALGraph*CreateALGraph()〃建表

!

inti,j,k;

floatm;

FILE*fp;

EdgeNode*s,*t;

ALGraph*G;

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

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

(

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

exit(1);

)

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

printf(〃請輸入頂點(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(〃請輸入第%d條邊的兩個端點(diǎn)序號，輸入格式為：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(〃請輸入第加條邊的對應(yīng)權(quán)值\n〃,k);

fscanf;〃保存邊信息，以無向網(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)生成最小生成樹模塊

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++)〃輸出最小生成樹信息

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è)施工的最佳方案\n");

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

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

printf；

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

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

G=CreateALGraph();〃建表

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

scanf("%d",&i);

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

//printfALGraph(G);

printf(〃\n〃)；

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

)

五、調(diào)試分析

1.設(shè)計與調(diào)試過程中遇到的問題分析、體會

1)一開始對文件讀寫操作不熟，采用從鍵盤輸出的方式驗證正確與否，對應(yīng)程序如下:

inti,j,k;

floatm;

EdgeNode*s,*t;

ALGraph*G;

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

printf(〃請輸入頂點(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(〃請輸入第%d條邊的兩個端點(diǎn)序號，輸入格式為：i,j\n〃,k);

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

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

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

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

scanfr%fzz,&m);〃保存邊信息，以無向網(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;

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

入，較為麻煩

-

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

85.6

請輸入第8條邊的兩個端點(diǎn)序號，輸入格式為：

5,7

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

10.5

請輸入第9條邊的兩個端點(diǎn)序號，輸入格式為：

37

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

56.4

請輸入第［。條邊的兩個端點(diǎn)序號，輸入格式為：

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

79.2

請輸入第11條邊的兩個端點(diǎn)序號,輸入格式為：

78

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

52.5

請輸入第12條邊的兩個端點(diǎn)序號,輸入格式為：

1,8

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

12.1

請輸入第13條邊的兩個端點(diǎn)序號,輸入格式為：i，j

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

8.?

請輸入第14條邊的兩個端點(diǎn)序號,輸入格式為：i，J

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

182

請輸入第15條邊的兩個端點(diǎn)序號,輸入格式為：i，j

3,5

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

41.1

輸入開始節(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)為檢驗所建立的無向網(wǎng)，編寫了一個輸出函數(shù)，輸出各個頂點(diǎn)以及與該頂點(diǎn)相鄰的其他

頂點(diǎn)以及對應(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〃)；

}

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

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

窈驗名稱：實驗三：管道鋪設(shè)施工的最佳方案

學(xué)號：031350102

姓名：王亞文

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

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

9,15

輸入開始節(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.主要算法的時間復(fù)雜度分析

六、使用說明

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

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

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

七、測試結(jié)果

|D：回漢

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

需驗名稱：實驗三：管道鋪設(shè)施工的最佳方案

學(xué)號：031350102

姓名：王亞文

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

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

輸入開始節(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）這個程序遇到的第一個主要問題是在建表過程，因為邊的頂點(diǎn)信息是大寫英文字母，一

開始我是用的ASCLL碼值，使用不方便，后來采用在定義時考慮多定義一個量，原程序：

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

j

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

EdgeTypeinfo;〃權(quán)值

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

}EdgeNode;

修正后的程序為:

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

t,1

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

vertexTypeadjvex;

EdgeTypeinfo;〃權(quán)值

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

}EdgeNode;

這樣多定義了一個量在后面的過程中會簡單許多，其次書上給的程序是生成有向網(wǎng)的，

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

無向網(wǎng)問題，但是一條邊重復(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ù)雖然語句較之前的多了5句但在輸入時少輸了一半的邊信息。其次解決耗時最

長的一個錯誤是在建表中，原程序：

typedefVertexNodeAdjlist[MaxVertexNum];

typedefstruct〃鄰接表

{

Adjlistadjlist;

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

intn;

inte;

}ALGraph;//ALGraph是以鄰接表方式存儲的圖類型

這個程序是抄的書上的，一開始不覺得書上的程序會是錯的，結(jié)果一直沒有看這個定義，在

輸入邊的信息時循環(huán)次數(shù)總是不對，一直嘗試著改動寫的輸入信息，弄了一下午也沒有搞定

這個問題，于是去求助研究生學(xué)長，下面是研究生學(xué)長發(fā)過來的郵件幫我指出錯誤所在，看

了學(xué)長的這封郵件后，重新改了一下自己的程序，修正后的程序為

typedefstruct〃鄰接表

!

VertexNodeadjlist[MaxVertexNum];

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

}ALGraph;//ALGraph是以鄰接表方式存儲的圖類型

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

面沒有定義Adjlist這個類型；|

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

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

CreateALGraph()

即ALGraph*CreateALGraph(VertexNode*adjlist);

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

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

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

快捷

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

3)在生成最小樹這個程序的編寫中，開始因為編程序是在老師講解生成樹之前，所以一開

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

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

生成樹，所以在編寫時主要研究的是用prim算法，在編寫prim算法時除了很多問題，例如

一開始我并沒有在循環(huán)中寫teed[i]=m;這句話，導(dǎo)致在最后輸出邊的信息時會有隨機(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)生可能是因為沒有賦值，所以加上teed[i]=m;這句話果然最后就輸出正確了，

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

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

最佳鋪設(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

中間編寫時問題不大，之前有看過prim算法的詳細(xì)介紹，所以在主思路上沒有太大的錯誤,

相對寫起來也比較順利。

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

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

八、附錄

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

#include<time.h>

〃輸入序號與字母對應(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];〃訪問變量,為一時表示未訪問

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

f

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

vertexTypeadjvex;

EdgeTypeinfo;〃權(quán)值

structnode*next;〃指向下一個鄰接點(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是以鄰接表方式存儲的圖類型

ALGraph*CreateALGraph()〃建表

inti,j,k;

floatm;

FILE*fp;

EdgeNode*s,*t;

ALGraph*G;

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

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

(

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

exit(1);

}

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

printf(〃請輸入頂點(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(〃請輸入第%(1條邊的兩個端點(diǎn)序號，輸入格式為：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(〃請輸入第%d條邊的對應(yīng)權(quán)值\n〃,k);

fscanf(fp,〃%f”,&m);〃保存邊信息，以無向網(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++)〃輸出最小生成樹信息

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