管道鋪設(shè)問題

1、實驗三：管道鋪設(shè)施工的最佳方案一. 問題描述1. 實驗題目：需要在某個城市n個居民小區(qū)之間鋪設(shè)煤氣管道，則在這n個居民小區(qū)之間只需要鋪設(shè) n-1條管道鋪設(shè)n-1條管道即可。假設(shè)任意兩個小區(qū)之間則可以鋪設(shè)管道，但由于地理環(huán)境不同，所需要的費用也不盡相同。選擇最優(yōu)的方案能使總投資盡可能小，這個問題即為求無向網(wǎng)的最小生成樹。2. 基本要求：在可能假設(shè)的m條管道中，選取n-1條管道，使得既能連通n個小區(qū)，又能使總投資最小。 每條管道的費用以網(wǎng)中該邊的權(quán)值形式給出，網(wǎng)的存儲采用鄰接表的結(jié)構(gòu)。3. 測試數(shù)據(jù)：使用下圖給出的無線網(wǎng)數(shù)據(jù)作為程序的輸入，求出最佳鋪設(shè)方案。二. 需求分析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 6 9 79.2 7 8 52.5 1 8 12.1 8 9 8.7 1 9 18.2 3 5 41.1三. 概要設(shè)計1. 所用到得數(shù)據(jù)結(jié)構(gòu)及其ADTtypedef struct node/邊表結(jié)點int NO;II鄰接點域；vertexType adjvex;EdgeType info;/權(quán)值struct node *n ext;/EdgeNode;typede

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

5、成樹模塊 void tree(ALGraph *G,i nt m)開始lsum=0; lowm=0; visitedm=0;ifi=1inNh-s=G- adjlistm.first edge;F1fYlowi=1000;teedi=m;i=1結(jié)束Vi+lows-NO=s- info; s=s-next;理Ymin=1000;j=1rIFN 十 in i=1f in ;x+jnvisitedj0&lowjadjlistk.firstedge輸出邊頂點信息i+ s!=NULL(visiteds-NO0&s-infoNOlows-NO=s-info;teeds-NO=k;s=s-next;函數(shù)調(diào)用

6、關(guān)系圖四、詳細設(shè)計1.實現(xiàn)每個操作的偽碼，重點語句加注釋1) 建表模塊ALGraph * CreateALGraph() /建表int i,j,k;float m;FILE *fp;EdgeNode *s,*t;ALGraph *G;fp=fope n( C:data.txt,廣);/打開文件if(fp=NULL)未找到文件prin tf(Ca nnt open the file!n ”);exit(1);G=(ALGraph *)malloc(sizeof(ALGraph);printf(”請輸入頂點數(shù)和邊數(shù)(輸入格式為：頂點數(shù) ,邊數(shù))n);scan f(%d,%d, &G- n,&G-e

7、);for(i=1;i n;i+)建立頂點信息G-adjlisti.vertex=fgetc(fp);G-adjlisti.firstedge=NULL;visitedi=i;for(k=1;ke;k+)/printf(請輸入第d條邊的兩個端點序號，輸入格式為：i,jn,k);/scan f(%d,%d, & i,&j);fscan f(fp,%d,&i);fscan f(fp,%d,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode);t=(EdgeNode *)malloc(sizeof(EdgeNode); printf(請輸入第4條邊的對應(yīng)權(quán)值n”,k);

8、fscan f(fp,%f,&m);保存邊信息，以無向網(wǎng)方式s-NO=j;s-adjvex=G-adjlistj.vertex;s-i nfo=m;s-n ext=G-adjlisti.firstedge;G-adjlisti.firstedge=s;t-NO=i;t-adjvex=G-adjlisti.vertex; t-i nfo=m;t-n ext=G-adjlistj.firstedge;G-adjlistj.firstedge=t;fclose(fp);/ 關(guān)閉文件 return G;2) 生成最小生成樹模塊void tree(ALGraph *G,i nt m)float low1

9、00;i nt teed100;int k,i,j;float min, sum=0;EdgeNode *s;lowm=0;visitedm=O;for(i=1;in ;i+)lowi=1000;teedi=m;s=G-adjlistm.firstedge;while(s!=NULL)數(shù)組初始化lows-NO=s-i nfo;s=s-n ext;for(i=1;in ;i+)min=1000;for(j=1;jn ;j+)找到最小權(quán)值if(visitedj0&lo wjadjlistk.firstedge;while(s!=NULL)找到最小權(quán)值if(visiteds-NO0&s-i nfoN

10、O) lows-NO=s-i nfo;teeds-NO=k;s=s-n ext;printf(最佳鋪設(shè)方案n);for(i=1;i n;i+)輸出最小生成樹信息if(i!=m)prin tf(”(d,%d)%.2ft,i,teedi,lowi);printf(”最小權(quán)值為：.2fn”,sum);3) 主函數(shù)模塊void mai n()ALGraph *G;int i;time_t rawtime;struct tm * timei nfo;time (&rawtime);timei nfo = localtime (&rawtime);printf(”實驗名稱：實驗三：管道鋪設(shè)施工的最佳方案n

11、);printf(”學(xué)號：031350102n ”);printf(”姓名：王亞文n);prin tf(=n);printf(”程序運行開始，);printf(Current local time and date:%s,asctime(timeinfo);G=CreateALGraph(); 建表printf(輸入開始節(jié)點n);scan f(%d,&i);tree(G,i); II生成最小樹/prin tfALGraph(G);prin tf(n ”);printf(Current local time and date:%s,asctime(timeinfo);五、調(diào)試分析1.設(shè)計與調(diào)試過

12、程中遇到的問題分析、體會1)一開始對文件讀寫操作不熟，采用從鍵盤輸出的方式驗證正確與否，對應(yīng)程序如下:int i,j,k;float m;EdgeNode *s,*t;ALGraph *G;G=(ALGraph *)malloc(sizeof(ALGraph);printf(”請輸入頂點數(shù)和邊數(shù)(輸入格式為：頂點數(shù) ，邊數(shù))n);scan f(%d,%d, &G- n,&G-e);for(i=1;i n;i+)建立頂點信息G-adjlisti.vertex=fgetc(fp);G-adjlisti.firstedge=NULL;visitedi=i;for(k=1;ke;k+)printf(請

13、輸入第d條邊的兩個端點序號，輸入格式為：i,jn”,k);sca nf(%d,%d, & i,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode);t=(EdgeNode *)malloc(sizeof(EdgeNode);printf(請輸入第4條邊的對應(yīng)權(quán)值n,k);scan f(%f,&m);保存邊信息，以無向網(wǎng)方式s-NO=j;s-adjvex=G-adjlistj.vertex;s-i nfo=m;s-n ext=G-adjlisti.firstedge;G-adjlisti.firstedge=s;t-NO=i;t-adjvex=G-adjlisti.

14、vertex; t-i nfo=m;t-n ext=G-adjlistj.firstedge;G-adjlistj.firstedge=t;return G;對應(yīng)截屏如下：發(fā)現(xiàn)這種方式輸入耗時長，而且在生成樹程序不正確時修改程序需要重復(fù)輸入，較為麻煩011)12-10C 44,60C3J25.9021.30 9,8)8.73輸出彳E” *C：USERSADMlNSTRATORDESKTOPyCLeDuqOCle亡的鄰接點尺權(quán)值：E 41-18 G EG.40 D的鄰接點及權(quán)值：F ?8_?0 E 67.30 C屯的鄰接點及權(quán)值，C 41,10 G 10.5R PF的鄰接點刃權(quán)值：I 79-20

15、 E 5.6O D時的鄰菽點及權(quán)值：HC 56.46 EH兇鄰接點坡權(quán)值：I S.7fl A 12.1fl CI的鄰接點尺權(quán)值：A 18.20 H 8.70 FPress any key to conit值12值2.輸霜7輸A0801B接遼接?0 sx nv 8 3 5-ixl45 rJ 勺 7WE NE f H I B c21.30 AB 5.90ue2)為檢驗所建立的無向網(wǎng)，編寫了一個輸出函數(shù)，輸出各個頂點以及與該頂點相鄰的其他頂點以及對應(yīng)權(quán)值，輸出函數(shù)為void prin tfALGraph(ALGraph *G)/輸出表int i;EdgeNode *s;printf(”輸出信息 n”

16、);for(i=1;in ;i+)printf(%c的鄰接點及權(quán)值:n”,G-adjlisti.vertex);s=G-adjlisti.firstedge;while(s!=NULL)prin tf(%c %.2f ,s-adjvex,s-i nfo);s=s-n ext;prin tf(n ”);輸出測試截屏如下證明從文件讀寫的與所需要建立的無向網(wǎng)相符2.主要算法的時間復(fù)雜度分析六、使用說明程序運行后，顯示提示信息：請輸入頂點數(shù)和邊數(shù)（輸入格式為：頂點數(shù)，邊數(shù)）之后程序從文件名為” C:data.txt讀入頂點信息和邊的信息，之后顯示提示信息輸入開始節(jié)點，執(zhí)行生成最小樹程序，輸出生成的最小

17、樹信息。七、測試結(jié)果3）這個程序遇到的第一個主要問題是在建表過程，因為邊的頂點信息是大寫英文字母,開始我是用的ASCLL碼值，使用不方便，后來采用在定義時考慮多定義一個量，原程序:typedef struct node/vertexType adjvex;EdgeType info;/struct node *n ext;/EdgeNode;修正后的程序為：typedef struct node/int NO;/vertexType adjvex;EdgeType info;/struct node *n ext;/邊表結(jié)點/鄰接點域；權(quán)值指向下一個鄰接點的指針域邊表結(jié)點鄰接點域；權(quán)值指向下一

18、個鄰接點的指針域EdgeNode;這樣多定義了一個量在后面的過程中會簡單許多，其次書上給的程序是生成有向網(wǎng)的,ke ;這樣雖然能解決開始我是考慮的將邊輸入兩邊，就是在循環(huán)時的終止條件設(shè)為無向網(wǎng)問題，但是一條邊重復(fù)輸入兩邊，較為麻煩，后期修正為:s-NO=j;s-adjvex=G-adjlistj.vertex;s-i nfo=m;s-n ext=G-adjlisti.firstedge;G-adjlisti.firstedge=s;t-NO=i;t-adjvex=G-adjlisti.vertex;t-i nfo=m;t-n ext=G-adjlistj.firstedge;G-adjlist

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

20、研究生學(xué)長發(fā)過來的郵件幫我指出錯誤所在，看了學(xué)長的這封郵件后，重新改了一下自己的程序，修正后的程序為typedef struct/鄰接表VertexNode adjlistMaxVertexNum;int n,e;II頂點數(shù)和邊數(shù)ALGraph;/ ALGraph是以鄰接表方式存儲的圖類型問題所在:結(jié)構(gòu)體ALGraphf紅色標記部分)中,-Adjlist adjlistf語句定義錯課正面沒有宇義Adjlist這個類舉；|解決方案：考慮在主函鞭main)中將全扃結(jié)構(gòu)體數(shù)組typedef VertexNode Adjl(5tMaxVerteMNium;中 AdJIkt 數(shù)組名作為參數(shù)進入 ALGr

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

22、al算法適合與邊稀疏的連通圖求解最小生成樹，所以在編寫時主要研究的是用prim算法，在編寫prim算法時除了很多問題，例如一開始我并沒有在循環(huán)中寫teedi=m;這句話，導(dǎo)致在最后輸出邊的信息時會有隨機數(shù)產(chǎn)嚴佳鋪設(shè)方峯32-8Q207,5)10.50生，截圖如下：5.9021.3041,1612.108.70最小權(quán)值為=211,6想到隨機數(shù)產(chǎn)生可能是因為沒有賦值，所以加上teedi=m;這句話果然最后就輸出正確了，再次在輸出時，產(chǎn)生的結(jié)果中有重復(fù)的一個節(jié)點，1000.00這個不應(yīng)該被輸出，所以考慮在輸出時加一個限制條件if(i!=m) 再次輸出就沒有了最佳鋪設(shè)方案tZ,lJ2-8079-230

23、(7.510.5012,109,8)8,70矗鬧就)吃11中間編寫時問題不大，之前有看過prim算法的詳細介紹，所以在主思路上沒有太大的錯誤, 相對寫起來也比較順利。2)建立鄰接表的復(fù)雜度為0(n+e);Prim算法的時間復(fù)雜度為O(elogn);八、附錄#in elude #in elude #i nclude #in elude /輸入序號與字母對應(yīng)關(guān)系A(chǔ)-1,B-2#defi ne MaxVertexNum 100typedef char vertexType;typedef float EdgeType;in t visited100;訪問變量，為一typedef struct nod

24、e/int NO;/vertexType adjvex;EdgeType info;/struct node *n ext;/EdgeNode;typedef struct vnode/vertexType vertex; /EdgeNode *firstedge; / VertexNode;typedef struct/VertexNode adjlistMaxVertexNum; int n,e;/ALGraph;/ ALGraphALGraph * CreateALGraph() /,C-3， D-4， E-5， F-6， G-7，H-8， 1-9時表示未訪問邊表結(jié)點鄰接點域；權(quán)值指向下

25、一個鄰接點的指針域頂點表節(jié)點頂點域編表頭指針鄰接表頂點數(shù)和邊數(shù)是以鄰接表方式存儲的圖類型建表float m;FILE *fp;EdgeNode *s,*t;ALGraph *G;fp=fope n( C:data.txt,廣);/打開文件if(fp=NULL)未找到文件prin tf(Ca nnt open the file!n ”);exit(1);G=(ALGraph *)malloc(sizeof(ALGraph);printf(”請輸入頂點數(shù)和邊數(shù)(輸入格式為：頂點數(shù) ，邊數(shù))n);scan f(%d,%d, &G- n,&G-e);for(i=1;i n;i+)建立頂點信息G-adj

26、listi.vertex=fgetc(fp);G-adjlisti.firstedge=NULL;visitedi=i;for(k=1;ke;k+)/printf(請輸入第d條邊的兩個端點序號，輸入格式為：i,jn,k);/scan f(%d,%d, & i,&j);fscan f(fp,%d,&i);fscan f(fp,%d,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode);t=(EdgeNode *)malloc(sizeof(EdgeNode);/ printf(請輸入第4條邊的對應(yīng)權(quán)值n”,k);fscan f(fp,%f,&m);保存邊信息，以無向

27、網(wǎng)方式s-NO=j;s-adjvex=G-adjlistj.vertex;s-i nfo=m;s-n ext=G-adjlisti.firstedge;G-adjlisti.firstedge=s;t-NO=i;t-adjvex=G-adjlisti.vertex;t-i nfo=m;t-n ext=G-adjlistj.firstedge;G-adjlistj.firstedge=t;fclose(fp);/ 關(guān)閉文件return G;void tree(ALGraph *G,int m)float low100;i nt teed100;int k,i,j;float min, sum=0

28、;EdgeNode *s;lowm=0;visitedm=0;for(i=1;in ;i+)lowi=1000;teedi=m;s=G-adjlistm.firstedge;while(s!=NULL)數(shù)組初始化lows-NO=s-i nfo;s=s-n ext;for(i=1;in ;i+)min=1000;for(j=1;jn ;j+)if(visitedj0&I owjadjlistk.firstedge;while(s!=NULL)if(visiteds-NO0&s-i nfoNO)找到最小權(quán)值lows-NO=s-i nfo;teeds-NO=k;s=s-n ext;printf(”最

29、佳鋪設(shè)方案n);for(i=1;i n;i+)輸出最小生成樹信息if(i!=m)prin tf(”(d,%d)%.2ft,i,teedi,lowi);printf(”最小權(quán)值為：.2fn”,sum);/*void prin tfALGraph(ALGraph *G)/輸出表int i;EdgeNode *s;printf(輸出信息 n”);for(i=1;in ;i+)printf(%c 的鄰接點及權(quán)值:n”,G-adjlisti.vertex);s=G-adjlisti.firstedge;while(s!=NULL)prin tf(%c %.2f ,s-adjvex,s-i nfo);s=

30、s-n ext;prin tf(n ”);*/void mai n()ALGraph *G;int i;time_t rawtime;struct tm * timei nfo;time (&rawtime);timei nfo = localtime (&rawtime);printf(”實驗名稱：實驗三：管道鋪設(shè)施工的最佳方案n);printf(”學(xué)號：031350102n ”);printf(姓名：王亞文n);prin tf(=n);printf(”程序運行開始，);printf(Current local time and date:%s,asctime(timeinfo);G=CreateAL