管道鋪設(shè)問題

1、實驗三：管道鋪設(shè)施工的最佳方案一.問題描述1.實驗題目：需要在某個城市n個居民小區(qū)之間鋪設(shè)煤氣管道，則在這n個居民小區(qū)之間只需要鋪設(shè)n-1條管道鋪設(shè)n-1條管道即可。假設(shè)任意兩個小區(qū)之間則可以鋪設(shè)管道，所需要的費用也不盡相同。選擇最優(yōu)的方案能使總投資盡可能小，最小生成樹。2 .基本要求：在可能假設(shè)的m條管道中，選取n-1條管道，使得既能連通n個小區(qū) 用以網(wǎng)中該邊的權(quán)值形式給出，網(wǎng)的存儲采用鄰接表的結(jié)構(gòu)。3 .測試數(shù)據(jù)：使用卜圖給出的無線網(wǎng)數(shù)據(jù)作為程序的輸入，求出最佳鋪設(shè)方案。但由于地理環(huán)境不同，這個問題即為求無向網(wǎng)的，又能使總投資最小。每條管道的費I參考解:二.需求分析1 .程序所能達到的基本

2、可能：在某個城市n個居民小區(qū)之間鋪設(shè)煤氣管道， 則在這n個居民小區(qū)之間只需要鋪設(shè)n-1條管道鋪設(shè)n-1條管道即可。假設(shè)任意兩個小區(qū)之間則可以鋪設(shè)管道，但由于地理環(huán)境不同， 所需要的費用也不盡相同。選擇最優(yōu)的方案能使總投資盡可能小，在可能假設(shè)的m條管道中，選取n-1條管道，使得既能連通n個小區(qū)，又能使總投資最小。2 .輸入輸出形式及輸入值范圍：程序運行后，顯示提示信息：請輸入頂點數(shù)和邊數(shù)（輸入格式為：頂點數(shù)，邊數(shù)）之后程序從文件名為"C:data.txt讀入頂點信息和邊的信息，之后 顯示提示信息輸入開始節(jié)點，執(zhí)行生成最小樹程序，輸出生成的最小樹信息。3 .測試數(shù)據(jù)要求：頂點數(shù)邊數(shù)為整數(shù)

3、，頂點信息為大寫字母，邊的權(quán)值為浮點型，C:data.txt 文件內(nèi)容為：ABCDEFGHI1 2 32.8 2 3 5.9 1 3 44.6 3 4 21.3 4 5 67.3 4 6 98.7 5 6 85.6 5 7 10.5 3 7 56.4 69 79.2 7 8 52.5 1 8 12.1 8 9 8.7 1 9 18.23541.1三.概要設(shè)計1.所用到得數(shù)據(jù)結(jié)構(gòu)及其ADTtypedef struct node/邊表結(jié)點int NO;II鄰接點域;vertexType adj vex;/ /EdgeType info; struct node *n ext;JEdgeNode;t

4、ypedef struct vnode(vertexType vertex; /EdgeNode *firstedge;/ JVertexNode;typedef struct/(VertexNode adjlistMaxVertexNum;int n,e;/JALGraph;/ ALGraph基本操作：ALGraph * CreateALGraph()2.主程序流程及其模塊調(diào)用關(guān)系1)主程序模塊權(quán)值指向下一個鄰接點的指針域頂點表節(jié)點頂點域編表頭指針鄰接表頂點數(shù)和邊數(shù)是以鄰接表方式存儲的圖類型/建表顯示主界面建表1生成最小樹k結(jié)束 建表模塊 ALGraph * CreateALGraph()開

5、始最小生成樹模塊 void tree(ALGraph *G,i nt m)開始sum=O;lowm=0;visitedm=O;J< s!=NULLlows->NO=s->info; s=s->next;s=G- >adjlistm.first edge;lowi=1000;teedi=m;min=1000;j=1JN輸出邊頂點信息s=G->adjlistk.firstedgesum+=min; visitedk=O;visitedj>0&&lowj<min/A s!=NULLmin=lowj;k=j；j+(visiteds->

6、;NO>0&as->info<lows->NOlows->NO=s->info;teeds->NO=k;函數(shù)調(diào)用笑系圖四、詳細設(shè)計1 .實現(xiàn)每個操作的偽碼，重點語句加注釋1)建表模塊ALGraph * CreateALGraph() /建表(int ij,k;float m;FILE *fp;EdgeNode *s,*t;ALGraph *G;fp=fope n( "C:data.txt"J廣)；打開文件if(fp=NULL)/未找到文件(prin tf("Ca nn't open the file!n &

7、quot;)；ex計；)G=(ALGraph *)malloc(sizeof(ALGraph);printf("請輸入頂點數(shù)和邊數(shù)(輸入格式為：頂點數(shù)，邊數(shù))n");scanf("%d,%d",&G->n,&G->e);for(i=1 ;iv=G->n;i+) 建立頂點信息(G->adjlisti.vertex=fgetc(fp);G->adjlisti.firstedge=NULL; visitedi=i;)for(k=1 ;k<=G->e;k+)(/ printf(,請輸入第1條邊的兩個端點序

8、號，輸入格式為：i,jn",k);/scanf("%d,%d",&i,&j);fscanf(fp,"%d",&i);fscanf(fp,"%d",&j);s=(EdgeNode *)malloc(sizeof(EdgeNode); t=(EdgeNode*)malloc(sizeof(EdgeNode); print"'請輸入第4條邊的對應權(quán)值n”,k);fscanf(fp,"f”,&m);保存邊信息，以無向網(wǎng)方式s->NO=j;s->adjve

9、x=G->adjlistj.vertex;s->info=m;s->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->adjvex=G->adjlisti.vertex;t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj.firstedge=t;fclose(fp);/ 關(guān)閉文件return G;)2)生成最小生成樹模塊void tree(ALGraph *G,int m)(float low100

10、;int teed100;int k,i,j;float min,sum=0;EdgeNode *s;lowm=0;visitedm=0;for(i=1 ;i<=G->n;i+)(lowi=1000;teedi=m;)s=G->adjlistm.firstedge;while(s!=NULL)數(shù)組初始化lows->NO=s->info;s=s->next;)for(i=1 ;i<G->n;i+)(min=1000;for(j=1 ;j<=G->n;j+)找到最小權(quán)值if(visitedj>0&&lowj<m

11、in)/ min=lowj；k=j；/標記節(jié)點)sum+=min;visitedk=O;s=G->adjlistk.firstedge;while(s!=NULL)(if(visiteds->NO>0&&s->info<lows->NO)/(lows->NO=s->info;teeds->NO=k;)s=s->next;)printfC,最佳鋪設(shè)方案W);for(i=1 ;iv=G->n;i+)輸出最小生成樹信息if(i!=m)printf("(%d,%d)%.2ft",i,teedi,low

12、i);printf(u 最小權(quán)值為:%.2fn'sum);)3)主函數(shù)模塊void main()(ALGraph *G;inti;time_t rawtime;struct tm * timeinfo;time (&rawtime);timeinfo = localtime (&rawtime);printf("實驗名稱：實驗三：管道鋪設(shè)施工的最佳方案printf("姓名：王亞文己）;找到最小權(quán)值n")；printf(“學號：031350102nH);An'*);printf("printf("程序運行開始，)p

13、rintf("Current local time and date:%s”,asctime(timeinfo);G=CreateALGraph();/ 建表printf("輸入開始節(jié)點W);scanf("d”,&i);tree(Gj); 生成最小樹/printfALGraph(G);printf("nH);printf("Current local time and date:%s”,asctime(timeinfo);)五、調(diào)試分析1.設(shè)計與調(diào)試過程中遇到的問題分析、體會1)一開始對文件讀寫操作不熟，采用從鍵盤輸出的方式驗證正確與否

14、，對應程序如下：int ij,k;float m;EdgeNode *s,*t;ALGraph *G;G=(ALGraph *)malloc(sizeof(ALGraph);printf("請輸入頂點數(shù)和邊數(shù)(輸入格式為：頂點數(shù)，邊數(shù))n");scanf("%d,%d",&G->n,&G->e);for(i=1 ;iv=G->n;i+) 建立頂點信息G->adjlisti.vertex=fgetc(fp);G->adjlisti.firstedge=NULL; visitedi=i;)for(k=1 ;k&l

15、t;=G->e;k+) (printf("請輸入第1條邊的兩個端點序號，輸入格式為：iJ'n'k);scanf("d,%d”,&i,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode);t=(EdgeNode *)malloc(sizeof(EdgeNode);printf(H請輸入第 4條邊的對應權(quán)值n”,k);scanf("%f”,&m);保存邊信息，以無向網(wǎng)方式s->NO=j;s->adjvex=G->adjlistj.vertex;s->info=m;s-&

16、gt;next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->adjvex=G->adjlisti.vertex;t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj.firstedge=t;)return G;)對應截屏如下：發(fā)現(xiàn)這種方式輸入耗時長，而且在生成樹程序不正確時修改程序需要重復輸 入，較為麻煩PAS；號 Hi二號疔|刃|.U:uPIMI目!I)輸入格式為. i-J輸入格式為：輸入格式為：i BvjNc輸入格:0

17、1邊的對應權(quán)11B接遼接|?0S XAO C 44,60C3j2>5.9011)12-10<4.3>21.30<9,8)8.73<5.3>輸出彳&的鄰接點尺權(quán)值：E41-10G S&.46D0的鄰接點及權(quán)值，F(xiàn)?8_?()E67.30C衛(wèi)的鄰接點及權(quán)值,C41,1()G10.5RPF的鄰接點刃權(quán)值：I79-20E85.60DG的鄰菽點及權(quán)值：HC 56.46 EH兇鄰接點坡權(quán)值：I S.7B A 12.H1 CI的鄰接點尺權(quán)值：11 18.20 H 8.70 FPress anv kev to cont2».21.30 AB 5.9

18、0.22)為檢驗所建立的無向網(wǎng)，編寫了一個輸出函數(shù)，輸出各個頂點以及與該頂點相鄰的其他頂點以及對應權(quán)值，輸出函數(shù)為void prin tfALGraph(ALGraph *G)/輸出表inti;EdgeNode *s;printf(H 輸出信息 n");for(i=1 ;i<=G->n;i+) printf("%c 的鄰接點及權(quán)值:nM,G->adjlisti.vertex); s=G->adjlisti.firstedge; while(s!=NULL)(printf("%c %.2f ”,s->adjvex,s>info);

19、s=s->next;)printf("nH);輸出測試截屏如下證明從文件讀寫的與所需要建立的無向網(wǎng)相符fC:USERSADMINISTRATODESKTCPVCDebugsa.exeI字號./實三,管道南設(shè)施工的最佳方案031350102姓名。王亞文程序運行開始.Current local tine and date：Thn 請端人頂點喊和邊數(shù)（輸入格式為，Nnu 12 1S：29：12201s頂點數(shù),邊數(shù)）谿攵開始節(jié)點1<9,8>8.90<6,9>79.20A的鄰接點及權(quán)值:<2.1>32.90<7,5)10.S0<3,2>

20、;5.90<8,1>12.10<4.3>21.30<9.8>8.70<G>3>41.19輸出信息118.20 H 12.18B的鄰接點及權(quán)值：CA 32.85日的鄰捂點及權(quán)值：E 41.10 G 56.4044.6021.3032.8044.60 B 5.90II休鄰接點及權(quán)值、，98.70 E 67.30的鄰接點及權(quán)值：21.30C 41el0 C 10.50F的鄰接點及權(quán)值：I 79.20 E 85606的鄰接點及權(quán)值：H 52.50 C 56.40H的鄰接點及權(quán)值：I 8.70 A 12.10I的鄰接點及權(quán)值： n 18.20 II

21、9.70 Current local tine85.6098.7010.5052.5079.20and date：Thu67.30Hov 12 15：29：122015ress any key to continue2.主要算法的時間復雜度分析六、使用說明程序運行后，顯示提示信息：請輸入頂點數(shù)和邊數(shù)（輸入格式為：頂點數(shù)，邊數(shù)）之后程序從文件名為" C:data.txt讀入頂點信息和邊的信息，之后顯示提示信息輸入開始節(jié)點，執(zhí)行生成最小樹程序，輸出生成的最小樹信息。七、測試結(jié)果，,管道鋪設(shè)施工的最任方案 字號,031357 R2lb： 3J = 44 2kllb家三序運彳 丁千干始，Cu

22、rrent _L ocal time and dateiTliu MOM號裔入頂點數(shù)和邊數(shù)（輸入格式如頂點數(shù)，邊數(shù)）餐人開始節(jié)點隈性鋪設(shè)方菜K±4>32-80<?,E>13.&G<3,2>5.?G<SA1>1£-10<4,3521.36<5,3>41.10v9,e?e .70最小權(quán)值為furrent local time and dateAThu Nov 12 15： 33=44 2B15 *ress anyp key to continue因為邊的頂點信息是大寫英文字母，一后來采用在定義時考慮多定義一個量

23、，原程序：邊表結(jié)點鄰接點域;3）這個程序遇到的第開嫡關(guān)圖g題是在建表過程權(quán)值的ASCLL碼值，typedef stru施用不方便，指向下一個鄰接點的指針域nodevertexType adjvex;EdgeType info;struct node *n ext;JEdgeNode;邊表結(jié)點/"鄰接點域;修正后的程序為：typedef struct node(int NO;權(quán)值指向下一個鄰接點的指針域JEdgeNode;這樣多定義了一個量在后面的過程中會簡單許多，其次書上給的程序是生成有向網(wǎng)的，-vertexType adjvex;EdgeType info;/開始我是考慮的將邊輸入

24、兩邊，就是在循環(huán)時的終止條件設(shè)為k<=2*G->e ;這樣雖然能解決無向網(wǎng)問題，但是一條邊重復輸入兩邊，較為麻煩，后期修正為：s->NO=j;s->adjvex=G->adjlistj.vertex;s->info=m;s->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->adjvex=G->adjlisti.vertex;t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj

25、.firstedge=t;修正后的函數(shù)雖然語句較之前的多了 5句但在輸入時少輸了一半的邊信息。其次解決耗時最長的一個錯誤是在建表中，原程序：鄰接表typedef VertexNode AdjlistMaxVertexNum;typedef structAdj list adjlist;/int n,e;頂點數(shù)和邊數(shù)int n;int e;JALGraph;/ ALGraph是以鄰接表方式存儲的圖類型這個程序是抄的書上的，一開始不覺得書上的程序會是錯的，結(jié)果一直沒有看這個定義，在輸入邊的信息時循環(huán)次數(shù)總是不對，一直嘗試著改動寫的輸入信息，弄了一下午也沒有搞定這個問題，于是去求助研究生學長，下面是

26、研究生學長發(fā)過來的郵件幫我指出錯誤所在，看了學長的這封郵件后，重新改了一下自己的程序，修正后的程序為typedef struct / 鄰接表VertexNode adjlistMaxVertexNum;int n,e;/頂點數(shù)和邊數(shù)JALGraph;/ ALGraph是以鄰接表方式存儲的圖類型語句定義錯謀，上聞題所在:結(jié)構(gòu)體ALGraph紅色標記靜分)中jAdjlist昭1也爐 面沒有宇義Adjlist這個類率；I 解決方案：考慮在主函鞭main)中將全扃結(jié)榕體數(shù)組typedefVertexNodeAdjl(5tMaxVerteMNium;中數(shù)組名作為參數(shù)進入ALGraph *CreateAL

27、Graph()町 ALGraph * CreatsALGraphfVertexNode * adjirst);將3adjW舌的訪惻方式史改為adjli$ti)G原因;該結(jié)構(gòu)體數(shù)組定義為全局結(jié)構(gòu)體 數(shù)紅無須通過ALGraph結(jié)構(gòu)佛播針G來訕鳳使用數(shù)組1S針VertewNode審mdjli眈方便程序修正后輸入正常了，就開始進入下一個階段生成最小樹的程序。3)在生成最小樹這個程序的編寫中，開始因為編程序是在老師講解生成樹之前，所以一開始是完全沒有地方下手，網(wǎng)上百度了一下如何生成最小樹，發(fā)現(xiàn)有兩種方法，Kruskal和prim算法，但研究生學長這個適合用prim算法，Kruskal算法適合與邊稀疏的連

28、通圖求解最小生成樹，所以在編寫時主要研究的是用prim算法，在編寫prim算法時除了很多問題，例如一開始我并沒有在循環(huán)中寫te6di=m;這句話，導致在最后輸出邊的信息時會有隨機數(shù)產(chǎn)生，截圖如下：<2r858993460>32.8Q20<7 5)1()5() I v3.2x.90<4,3>2L30 v5,3>41,16，|<8 r3589934G0>12.10v9,8>8.70 最小權(quán)值為二211,6想到隨機數(shù)產(chǎn)生可能是因為沒有賦值，所以加上teedi=m;這句話果然最后就輸出正確了，再次在輸出時，產(chǎn)生的結(jié)果中有重復的一個節(jié)點，<1,

29、1 >1000.00這個不應該被輸出，所以考慮在輸出時加一個限制條件i f ( i ! = m ) 再次輸出就沒有了最佳鋪設(shè)方案tZ,l>J2-80<6f9>79-23(7.5>10.50<8,1>12,10<9,8)8,70矗 洞就)口乞 11 J中間編寫時問題不大，之前有看過prim算法的詳細介紹，所以在主思路上沒有太大的錯誤，相對寫起來也比 較順利。2)建立鄰接表的復雜度為0(n+e);Prim算法的時間復雜度為O(elogn);八、附錄#include <stdio.h>#include <malloc.h>#in

30、clude <stdlib.h>時表示未訪問，C-3，D-4，E-5，F(xiàn)-6，G-7，H-8，1-9輸入序號與字母對應關(guān)系A(chǔ)-1B-2#define MaxVertexNum 100 typedef char vertexType;typedef float EdgeType;邊表結(jié)點struct node /int NO; / vertexType adjvex;鄰接點域；EdgeType info;/struct node *next;/權(quán)值JEdgeNode;指向下一個鄰接點的指針域typedef struct vnode /頂點表節(jié)點vertexType vertex;/E

31、dgeNode *firstedge;頂點域/ JVertexNode;編表頭指針鄰接表int visited100; 訪問變量，為一 typedeftypedef struct /VertexNode adjlistMaxVertexNum;頂點數(shù)和邊數(shù)int n,e;/是以鄰接表方式存儲的圖類型JALGraph;/ ALGraphALGraph * CreateALGraph()/建表intfloat m;FILE *fp;EdgeNode *s,*t;ALGraph *G;fp=f。pen(”C:data.txtTr");打開文件if(fp=NULL)/未找到文件(printf

32、("Cann't open the file!n"); exit(1);)G=(ALGraph *)malloc(sizeof(ALGraph);printf("請輸入頂點數(shù)和邊數(shù)(輸入格式為：頂點數(shù)，邊數(shù))nu);scanf(',%d,%d,&G->n,&G->e);for(i=1 ;iv=G->n;i+) 建立頂點信息(G->adjlisti.vertex=fgetc(fp);G->adjlisti.firstedge=NULL; visitedi=i;for(k=1 ;k<=G->e;

33、k+)(/ printf(,1請輸入第% d條邊的兩個端點序號，輸入格式為：/scanf(H%d,%d",&i,&j);fscanf(fpcT,&i);fscanf(fp/d”,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode); t=(EdgeNode*)malloc(sizeof(EdgeNode);/ printf(u請輸入第% 4條邊的對應權(quán)值n”,k);fscanf(fp,"R&m);保存邊信息，以無向網(wǎng)方式s->NO=j;s->adjvex=G->adjlistj.vert

34、ex;s->info=m;s->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->adjvex=G->adjlisti.vertex;t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj.firstedge=t;)fclose(fp);/ 關(guān)閉文件return G;void tree(ALGraph *GJnt m) (float low100;int teed100;int kJJ;float min,s

35、um=0;EdgeNode *s;lowm=0;visitedm=0;for(i=1 ;i<=G->n;i+)(lowi=1000;teedi=m; s=G->adjlistm.firstedge; while(s!=NULL)/ 數(shù)組初始化lows->NO=s->info;s=s->next;for(i=1 ;i<G->n;i+)(min=1000;for(j=1 ;j<=G->n;j+)(if(visitedj>0&&lowj<min)/ 找到最小權(quán)值(min=lowj；k=j；/標記節(jié)點)sum+=m

36、in;visitedk=O;s=G->adjlistk.firstedge;while(s!=NULL)(if(visiteds->NO>0&&s->info<lows->NO)/ 找到最小權(quán)值( lows->NO=s->info;teeds->NO=k;)s=s->next;printf("最佳鋪設(shè)方案n");for(i=1 ;iv=G->n;i+)輸出最小生成樹信息if(i!=m)printf("(%d,%d)%.2ft"Ji,teedi,lowi);printf(&q

37、uot;最小權(quán)值為:%.2fn'sum);)/*void printfALGraph(ALGraph *G) / 輸出表int i;EdgeNode *s;printf("輸出信息 n”)；for(i=1 ;iv=G->n;i+)(printf("%c 的鄰接點及權(quán)值:n",G->adjlisti.vertex);s=G->adjlisti.firstedge;while(s!=NULL)(printf("%c %.2f ”,s->adjvex,s->info);s=s->next;)printf("nn);)7void main()(ALGraph *G;int i;time_t rawtime;struct tm * timeinfo;time (&rawtime);timeinfo = localtime (&rawtime);pri