管道鋪設(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)及其ADT typedef struct node /邊表結(jié)點int NO; /鄰接點域; vertexType adjvex;EdgeType info; /權(quán)值struct node *next; /指向下一個鄰接點的指針域EdgeNo

4、de;typedef struct vnode /頂點表節(jié)點vertexType vertex; /頂點域EdgeNode *firstedge; /編表頭指針VertexNode;typedef struct /鄰接表 VertexNode adjlistMaxVertexNum;int n,e; /頂點數(shù)和邊數(shù)ALGraph; / ALGraph是以鄰接表方式存儲的圖類型基本操作：ALGraph * CreateALGraph() /建表2. 主程序流程及其模塊調(diào)用關(guān)系 1) 主程序模塊建表模塊ALGraph * CreateALGraph() 最小生成樹模塊void tree(ALGra

5、ph *G,int m) 函數(shù)調(diào)用關(guān)系圖 四、 詳細設(shè)計 1. 實現(xiàn)每個操作的偽碼，重點語句加注釋 1）建表模塊ALGraph * CreateALGraph() /建表int i,j,k;float m;FILE *fp;EdgeNode *s,*t;ALGraph *G;fp=fopen("C:data.txt","r");/打開文件if(fp=NULL)/未找到文件printf("Cann't open the file!n");exit(1); G=(ALGraph *)malloc(sizeof(ALGraph);p

6、rintf("請輸入頂點數(shù)和邊數(shù)（輸入格式為：頂點數(shù),邊數(shù)）n");scanf("%d,%d",&G->n,&G->e);for(i=1;i<=G->n;i+)/建立頂點信息 G->adjlisti.vertex=fgetc(fp);G->adjlisti.firstedge=NULL;visitedi=i;for(k=1;k<=G->e;k+) /printf("請輸入第%d條邊的兩個端點序號，輸入格式為：i,jn",k);/scanf("%d,%d"

7、;,&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->adjlistj.vertex; s->inf

8、o=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;int teed100;int k,i,j;float min,s

9、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;/標(biāo)記節(jié)點 sum+=mi

10、n;visitedk=0;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;i<=G->n;i+)/輸出最小生成樹信息 if(i!=m) printf("(%d,%d)%.2ft",i,teedi,lowi); printf(

11、"最小權(quán)值為:%.2fn",sum);3） 主函數(shù)模塊 void main() ALGraph *G;int i;time_t rawtime;struct tm * timeinfo; time (&rawtime);timeinfo = localtime (&rawtime); printf(" 實驗名稱：實驗三：管道鋪設(shè)施工的最佳方案n");printf(" 學(xué)號：031350102n"); printf(" 姓名：王亞文n"); printf("=n");printf(

12、"程序運行開始，");printf("Current local time and date:%s",asctime(timeinfo);G=CreateALGraph();/建表printf("輸入開始節(jié)點n");scanf("%d",&i); tree(G,i);/生成最小樹/printfALGraph(G); printf("n");printf("Current local time and date:%s",asctime(timeinfo);五、 調(diào)試分析

13、 1. 設(shè)計與調(diào)試過程中遇到的問題分析、體會 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");scanf("%d,%d",&G->n,&G->e);for(i=1;i<=G->n;i+)/建立頂點信息 G->adjlisti.vertex=fgetc(

14、fp);G->adjlisti.firstedge=NULL;visitedi=i;for(k=1;k<=G->e;k+) printf("請輸入第%d條邊的兩個端點序號，輸入格式為：i,jn",k); scanf("%d,%d",&i,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode);t=(EdgeNode *)malloc(sizeof(EdgeNode); printf("請輸入第%d條邊的對應(yīng)權(quán)值n",k);scanf("%f",&

15、m);/保存邊信息，以無向網(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.firstedge=t;return G;對應(yīng)截屏如下：發(fā)現(xiàn)這種方式輸入耗時長，而且在生成樹程序不正

16、確時修改程序需要重復(fù)輸入，較為麻煩2）為檢驗所建立的無向網(wǎng)，編寫了一個輸出函數(shù)，輸出各個頂點以及與該頂點相鄰的其他頂點以及對應(yīng)權(quán)值，輸出函數(shù)為void printfALGraph(ALGraph *G) /輸出表int i;EdgeNode *s;printf("輸出信息n"); for(i=1;i<=G->n;i+)printf("%c的鄰接點及權(quán)值:n",G->adjlisti.vertex);s=G->adjlisti.firstedge;while(s!=NULL)printf("%c %.2f ",s

17、->adjvex,s->info);s=s->next;printf("n");輸出測試截屏如下證明從文件讀寫的與所需要建立的無向網(wǎng)相符2. 主要算法的時間復(fù)雜度分析 六、 使用說明程序運行后，顯示提示信息：請輸入頂點數(shù)和邊數(shù)（輸入格式為：頂點數(shù),邊數(shù)）之后程序從文件名為”C:data.txt讀入頂點信息和邊的信息，之后顯示提示信息輸入開始節(jié)點，執(zhí)行生成最小樹程序，輸出生成的最小樹信息。七、 測試結(jié)果 3） 這個程序遇到的第一個主要問題是在建表過程，因為邊的頂點信息是大寫英文字母，一開始我是用的ASCLL碼值，使用不方便，后來采用在定義時考慮多定義一個量，

18、原程序：typedef struct node /邊表結(jié)點vertexType adjvex; /鄰接點域; EdgeType info; /權(quán)值struct node *next; /指向下一個鄰接點的指針域EdgeNode;修正后的程序為：typedef struct node /邊表結(jié)點int NO; /鄰接點域; vertexType adjvex;EdgeType info; /權(quán)值struct node *next; /指向下一個鄰接點的指針域EdgeNode;這樣多定義了一個量在后面的過程中會簡單許多，其次書上給的程序是生成有向網(wǎng)的， 一開始我是考慮的將邊輸入兩邊，就是在循環(huán)時的

19、終止條件設(shè)為k<=2*G->e；這樣雖然能解決無向網(wǎng)問題，但是一條邊重復(fù)輸入兩邊，較為麻煩，后期修正為：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.firstedg

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

21、過來的郵件幫我指出錯誤所在，看了學(xué)長的這封郵件后，重新改了一下自己的程序，修正后的程序為typedef struct /鄰接表 VertexNode adjlistMaxVertexNum;int n,e; /頂點數(shù)和邊數(shù)ALGraph; / ALGraph是以鄰接表方式存儲的圖類型程序修正后輸入正常了，就開始進入下一個階段生成最小樹的程序。3） 在生成最小樹這個程序的編寫中，開始因為編程序是在老師講解生成樹之前，所以一開始是完全沒有地方下手，網(wǎng)上百度了一下如何生成最小樹，發(fā)現(xiàn)有兩種方法，Kruskal和prim算法，但研究生學(xué)長這個適合用prim算法，Kruskal算法適合與邊稀疏的連通圖求

22、解最小生成樹，所以在編寫時主要研究的是用prim算法，在編寫prim算法時除了很多問題，例如一開始我并沒有在循環(huán)中寫teedi=m;這句話，導(dǎo)致在最后輸出邊的信息時會有隨機數(shù)產(chǎn)生，截圖如下：想到隨機數(shù)產(chǎn)生可能是因為沒有賦值，所以加上teedi=m;這句話果然最后就輸出正確了，再次在輸出時，產(chǎn)生的結(jié)果中有重復(fù)的一個節(jié)點，<1,1>1000.00這個不應(yīng)該被輸出，所以考慮在輸出時加一個限制條件if(i!=m)再次輸出就沒有了，中間編寫時問題不大，之前有看過prim算法的詳細介紹，所以在主思路上沒有太大的錯誤，相對寫起來也比較順利。2） 建立鄰接表的復(fù)雜度為O(n+e); Prim算法的

23、時間復(fù)雜度為O(elogn);八、 附錄 #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <time.h> /輸入序號與字母對應(yīng)關(guān)系A(chǔ)-1,B-2，C-3，D-4，E-5，F(xiàn)-6，G-7，H-8，I-9#define MaxVertexNum 100typedef char vertexType;typedef float EdgeType;int visited100;/訪問變量，為一時表示未訪問typedef struct node /邊表結(jié)點int NO

24、; /鄰接點域; vertexType adjvex;EdgeType info; /權(quán)值struct node *next; /指向下一個鄰接點的指針域EdgeNode;typedef struct vnode /頂點表節(jié)點vertexType vertex; /頂點域EdgeNode *firstedge; /編表頭指針VertexNode;typedef struct /鄰接表 VertexNode adjlistMaxVertexNum;int n,e; /頂點數(shù)和邊數(shù)ALGraph; / ALGraph是以鄰接表方式存儲的圖類型ALGraph * CreateALGraph() /建

25、表int i,j,k;float m;FILE *fp;EdgeNode *s,*t;ALGraph *G;fp=fopen("C:data.txt","r");/打開文件if(fp=NULL)/未找到文件printf("Cann't open the file!n");exit(1); G=(ALGraph *)malloc(sizeof(ALGraph);printf("請輸入頂點數(shù)和邊數(shù)（輸入格式為：頂點數(shù),邊數(shù)）n");scanf("%d,%d",&G->n,&am

26、p;G->e);for(i=1;i<=G->n;i+)/建立頂點信息 G->adjlisti.vertex=fgetc(fp);G->adjlisti.firstedge=NULL;visitedi=i;for(k=1;k<=G->e;k+) /printf("請輸入第%d條邊的兩個端點序號，輸入格式為：i,jn",k);/scanf("%d,%d",&i,&j);fscanf(fp,"%d",&i);fscanf(fp,"%d",&j);s

27、=(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->adjlistj.vertex; s->info=m;s->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->

28、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 *G,int m)float low100;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

29、.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;/標(biāo)記節(jié)點 sum+=min;visitedk=0;s=G->adjlistk.firstedge;while(s!=NULL)if(visiteds->NO>0&&s->inf

30、o<lows->NO)/找到最小權(quán)值lows->NO=s->info;teeds->NO=k;s=s->next; printf("最佳鋪設(shè)方案n"); for(i=1;i<=G->n;i+)/輸出最小生成樹信息 if(i!=m) printf("(%d,%d)%.2ft",i,teedi,lowi); printf("最小權(quán)值為:%.2fn",sum);/*void printfALGraph(ALGraph *G) /輸出表int i;EdgeNode *s;printf("

31、;輸出信息n"); for(i=1;i<=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("n");*/void main() ALGraph *G;int i;time_t rawtime;struct tm * timeinfo; time (&rawtime);timeinfo = localtime (&rawtime); printf(" 實驗名稱：實驗三：管道鋪設(shè)施工的最佳方案n");printf(" 學(xué)號：031350102n"); printf(" 姓名：王亞文n"); printf("=n");printf("程序運行開始，");printf("Current local time and date:%s",asctime(