實驗三：管道鋪設施工的最佳方案

一.問題描述

1.實驗題目：

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

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

所需要的費用也不盡相同。選擇最優的方案能使總投資盡可能小，這個問題即為求無向網的

最小生成樹。

2.基本要求：

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

每條管道的費用以網中該邊的權值形式給出，網的存儲采用鄰接表的結構。

3.測試數據：

使用下圖給出的無線網數據作為程序的輸入，求出最佳鋪設方案。

98.7

參考解:

二.需求分析

1.程序所能達到的基本可能：

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

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

需要的費用也不盡相同。選擇最優的方案能使總投資盡可能小，在可能假設的m條管道中，

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

2.輸入輸出形式及輸入值范圍：程序運行后，顯示提示信息：請輸入頂點數和邊數（輸入格

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

顯示提示信息輸入開始節點，執行生成最小樹程序，輸出生成的最小樹信息。

3.測試數據要求：頂點數邊數為整數，頂點信息為大寫字母，邊的權值為浮點型，

C:\\data.txt文件內容為:ABCDEFGHI

1232.8235.91344.63421.34567.34698.75685.65710.53756.46

979.27852.51812.1898.71918.23541.1

三.概要設計

1.所用到得數據結構及其ADT

typedefstructnode〃邊表結點

intNO;〃鄰接點域;

vertexTypeadjvex;

EdgeTypeinfo;〃權值

structnode*next;〃指向下一個鄰接點的指針域

}EdgeNode;

typedefstructvnode〃頂點表節點

(

vertexTypevertex;〃頂點域

EdgeNode*firstedge;〃編表頭指針

}VertexNode;

typedefstruct〃鄰接表

VertexNodeadjlist[MaxVertexNum];

intn,e;〃頂點數和邊數

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

基本操作：ALGraph*CreateALGraphO〃建表

2.主程序流程及其模塊調用關系

建表模塊ALGraph*CreateALGraph()

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

函數調用關系圖

四、詳細設計

1.實現每個操作的偽碼，重點語句加注釋

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(〃請輸入頂點數和邊數(輸入格式為：頂點數，邊數)\n〃)；

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

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

(

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

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

visited[i]=i;

}

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

(

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

fscanf;〃保存邊信息，以無向網方式

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);〃關閉文件

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)〃數組初始化

(

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)〃找到最小權值

min=low[j];

k=j;〃標記節點

)

}

sum+=min;

visited[k]=O;

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

while(s!=NULL)

(

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

(

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

teed[s->N0]=k;

)

s=s->next;

)

}

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

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

if(i!=m)

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

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

)

3)主函數模塊

voidmain()

!

ALGraph*G;

inti;

timetrawtime;

structtm*timeinfo;

time(&rawtime);

timeinfo=localtime(ftrawtime);

printfC實驗名稱：實驗三：管道鋪設施工的最佳方案\n");

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

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

printf；

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

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

G=CreateALGraph();〃建表

printf(〃輸入開始節點\n〃);

scanf("%d",&i);

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

//printfALGraph(G);

printf(〃\n〃)；

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

)

五、調試分析

1.設計與調試過程中遇到的問題分析、體會

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

inti,j,k;

floatm;

EdgeNode*s,*t;

ALGraph*G;

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

printf(〃請輸入頂點數和邊數(輸入格式為：頂點數，邊數)\n〃)；

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

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

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

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

visited[i]=i;

i

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

(

printf(〃請輸入第%d條邊的兩個端點序號，輸入格式為：i,j\n〃,k);

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

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

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

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

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

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;

對應截屏如下：發現這種方式輸入耗時長，而且在生成樹程序不正確時修改程序需要重復輸

入，較為麻煩

-

睛輸入第7條邊的對應權值

85.6

請輸入第8條邊的兩個端點序號，輸入格式為：

5,7

請輸入第8條邊的對應權值

10.5

請輸入第9條邊的兩個端點序號，輸入格式為：

37

宿輸入第9條邊的對應權值

56.4

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

德輸入第條邊的對應權值

79.2

請輸入第11條邊的兩個端點序號,輸入格式為：

78

港輸入第11條邊的對應權值

52.5

請輸入第12條邊的兩個端點序號,輸入格式為：

1,8

請輸入第12條邊的對應權值

12.1

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

褊｝入第13條邊的對應權值

8.?

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

善徐入第14條邊的時應權值

182

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

3,5

請輸入第15條邊的對應權值

41.1

輸入開始節點

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的鄰接點及權值;

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

B的鄰接點及權值:

5.90A32.80

的鄰接點及權值B!:

C的鄰接點及權值：

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

D的鄰接點及權值：

F98.70E67.30C21.30

E的鄰接點及權值：

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

F的鄰接點及權值：

I79.20E85.60D98.70

G的鄰接點及權值：

H52.50C56.4010.50

H的鄰接點及權值：

I8.70A12.10G52.50

I的鄰接點及權值：

h18.20H8.7079.20

pressanykeytocontinue

2)為檢驗所建立的無向網，編寫了一個輸出函數，輸出各個頂點以及與該頂點相鄰的其他

頂點以及對應權值，輸出函數為voidprintfALGraph(ALGraph*G)〃輸出表

inti;

EdgeNode*s;

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

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

(

printf(z，%c的鄰接點及權值:\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〃)；

}

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

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

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

學號：031350102

姓名：王亞文

行呈序運彳丁開始，Currentlocaltimeanddate：ThuNou1215:29:122015

情輸入頂點數和邊數（輸入格式為:頂點數，邊數）

9,15

輸入開始節點

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的鄰接點及權值:

I18.20H12.1044.60B32.80

B的鄰接點及權值：

C5.90A32.80

C的鄰接點及權值：

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

D的鄰接點及權值：

F98.70E67.3021.30

E的鄰接點及權值：

C41.10G10.50F85.6067.30

F的鄰接點及權值：

I79.20E85.60D98.70

G的鄰接點及權值：

H52.5056.4010.50

H的鄰接點及權值：

I8.?0A12.10

I的鄰接點及權值：

A18.20H8.70F79.20

(Currentlocaltineanddate：ThuNou1215:29:122015

Pressanykeytocontinue

2.主要算法的時間復雜度分析

六、使用說明

程序運行后，顯示提示信息：請輸入頂點數和邊數（輸入格式為：頂點數，邊數）之后程序

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

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

七、測試結果

|D：回漢

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

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

學號：031350102

姓名：王亞文

程序達彳丁開始，Currentlocaltimeanddate：ThuNou1215：33：442015

請輸入頂點數和邊數（輸入格式為：頂點數，邊數）

輸入開始節點

￡佳鋪設方案

<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最小權值為：211.60

Currentlocaltineanddate：ThuNou1215：33：442015

Pressanykeytocontinue

3）這個程序遇到的第一個主要問題是在建表過程，因為邊的頂點信息是大寫英文字母，一

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

typedefstructnode〃邊表結點

j

vertexTypeadjvex;〃鄰接點域；

EdgeTypeinfo;〃權值

structnode*next;〃指向下一個鄰接點的指針域

}EdgeNode;

修正后的程序為:

typedefstructnode〃邊表結點

t,1

intNO;〃鄰接點域；

vertexTypeadjvex;

EdgeTypeinfo;〃權值

structnode*next;〃指向下一個鄰接點的指針域

}EdgeNode;

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

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

無向網問題，但是一條邊重復輸入兩邊，較為麻煩，后期修正為：

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;

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

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

typedefVertexNodeAdjlist[MaxVertexNum];

typedefstruct〃鄰接表

{

Adjlistadjlist;

//intn,e;〃頂點數和邊數

intn;

inte;

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

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

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

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

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

typedefstruct〃鄰接表

!

VertexNodeadjlist[MaxVertexNum];

intn,e;〃頂點數和邊數

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

問題所在:結構體ALGraph(紅色標記部分)中，"Adjlistadjlistf語句定義錯誤，上

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

解決方案：考慮在主函數main()中將全局結構體數組typedefVertexNode

AdjlistfMaxVertexNum];中Adjlist數組名作為參數進入ALGraph*

CreateALGraph()

即ALGraph*CreateALGraph(VertexNode*adjlist);

將的訪問方式更改為原因:該結構體數組定義為全局結構體

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

數組無須通過ALGraph結構體指針G來訪同使用數組指針VertexNode*adjlist方便

快捷

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

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

始是完全沒有地方下手，網上百度了一下如何生成最小樹，發現有兩種方法,Kruskal和prim

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

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

一開始我并沒有在循環中寫teed[i]=m;這句話，導致在最后輸出邊的信息時會有隨機數產

生，截圖如下：

最佳鋪設方案

(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最小權值為

想到隨機數產生可能是因為沒有賦值，所以加上teed[i]=m;這句話果然最后就輸出正確了，

再次在輸出時，產生的結果中有重復的一個節點，<1,D1000.00這個不應該被輸出，所以

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

最佳鋪設方案

<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最小權值為

0

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

相對寫起來也比較順利。

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

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

八、附錄

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

#include<time.h>

〃輸入序號與字母對應關系AT,,B-2,C-3,D-4,E-5,F-6,G-7,H-8,1-9

#defineMaxVertexNum100

typedefcharvertexType;

typedeffloatEdgeType;

intvisited[100];〃訪問變量,為一時表示未訪問

typedefstructnode〃邊表結點

f

intNO;〃鄰接點域；

vertexTypeadjvex;

EdgeTypeinfo;〃權值

structnode*next;〃指向下一個鄰接點的指針域

}EdgeNode;

typedefstructvnode〃頂點表節點

if

vertexTypevertex;〃頂點域

EdgeNode*firstedge;〃編表頭指針

}VertexNode;

typedefstruct〃鄰接表

VertexNodeadjlist[MaxVertexNum];

intn,e;〃頂點數和邊數

}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(〃請輸入頂點數和邊數(輸入格式為：頂點數，邊數)\n〃)；

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

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

(

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

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

visited[i]=i;

1

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

(

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

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

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);〃關閉文件

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)〃數組初始化

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)〃找到最小權值

(

min=low[j];

k=j;〃標記節點

)

}

sum+二min;

visited[k]=O;

s=G->adjlist[kJ.firstedge;

while(s!=NULL)

(

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

(

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

teed[s->N0]zzk;

}

s=s->next;

)

)

printf（〃最佳鋪設方案\n〃）;

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

if(i!=m)

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

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

)

AvoidprintfALGraph(ALGraph*G)〃輸出表

{

inti;

EdgeNode*s;

printf(〃輸出信息信");

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

(

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

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

while(s!=NULL)

(

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