管道鋪設施工的最佳方案問題

1．問題描述：

1.實驗題目：

需要在某個城市n個居民小區之間鋪設煤氣管道，則在這n個居民小區之間只需要鋪設n-1條管道即可。假設任意兩個小區之間都可以鋪設管道，但由於地理環境不同，所需要的費用也不盡相同。選擇最優的方案能使總投資盡可能小，這個問題即為求無向網的最小生成樹。

2.基本要求：

在可能假設的m條管道中，選取n-1條管道，使得既能連通n個小區，又能使總投資最小。每條管道的費用以網中該邊的權值形式給出，網的儲存採用鄰接表的結構。

3.測試資料：

使用下圖給出的無線網資料作為程式的輸入，求出最佳鋪設方案。右側是給出的參考解。

4.簡述每一部分的物件、目的和要求：

.主函式部分：

物件：圖g；

目的：為圖g分配空間，以作為後續呼叫函式的引數；

要求：無。

. create_algraph( )函式部分：

物件：頂點，邊及其權值；

目的：將頂點，邊存放在一起，構成圖；

要求：構造頂點表，各頂點的鄰接表以構造圖。

. create_wlgraph( )函式部分：

物件：圖g；

目的：將圖中的權值只存放一次，存放到w指向的結構體中；

要求：權值只存放一次，再分別存放該邊的左右頂點。

. select_info( )函式部分：

物件：w指向的結構體；

目的：將該結構體中的各權值以公升序排列；

要求：採用簡單選擇法進行排序。

. create_tlgraph( )函式部分：

物件：排序後的w指向的結構體；

目的：找到構成最小生成樹的邊；

要求：依權值公升序排列，判斷各邊是否構成迴路來取捨各邊。

2．需求分析

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

在n個小區m條管道中，選取n-1條管道，實現連通這n個小區，同時權值之和為最小。

2.輸入輸出形式及輸入值範圍：

程式執行後，使用者可根據提示資訊："please input the vertices and the edges:"輸入頂點數和邊數，再根據提示資訊：

"please input the information of the vertices:"輸入頂點資訊，然後進入迴圈，建立各個頂點的鄰接表，即根據提示資訊"please input the information of edges:"和"please input the information of weight:

"依次輸入各頂點與其他頂點本身以及兩者之間的權值，建立圖完畢。使用者輸入完畢後，程式自動輸出執行結果。輸入值必須為字母和浮點數，可以不必區分大小寫。

3.測試資料要求：

使用者輸入字母時，輸入大寫或小寫，都可以被該程式識別，正常執行。但必須根據提示資訊後面給出的參考形式，有針對性地輸入逗號。

3．概要設計

為了實現上述功能，該程式以鄰接表來儲存圖，因此需要圖這個抽象資料型別。

1. 圖抽象資料型別定義：

adt algraph

資料關係：r=;

基本操作：create_algraph(g)；//建立圖

create_wlgraph(g)； //將圖g中各頂點以及權值存放到新圖中，權值只存放一次

select_info(w, g)；//將新圖w中的權值按公升序排列

create_tlgraph(w, g)；//將最小生成樹以頂點對（i, j）的形式輸出

}adt algraph

2.本程式保護模組：

主函式模組

圖模組呼叫關係：

3.主要演算法流程圖：

create_algraph( )演算法流程圖create_wlgraph()演算法流程圖：

create_tlgraph( )演算法流程圖：

4．詳細設計

1.相關標頭檔案的呼叫說明：

#include

#define maxvernum 100

2.元素型別、結點型別和結點指標型別：

static void forcefloat(float *p)

typedef struct node

edgenode;

typedef struct vnode

vertexnode;

typedef vertexnode adjlist[maxvernum];

struct bian

;typedef struct

wgraph;

struct visit

3.鄰接表型別：

typedef struct

algraph;

//部分基本操作的偽碼實現

create_algraph(algraph *g)

for(k=0;k<2*(g->e);k++)

/* printf("please output the information:\n");

printf("%d,%d\n",g->n,g->e);

printf("x=%d\n",x);

for(i=0;in;i++)

}*/}int panduan_vertex(int k,int i,wgraph *w,edgenode *s)

void select_info(wgraph *w,algraph *g)

}/*for (i=0;i<(g->e);i++)

printf("%.1f ",w->e[i].info);

printf("\n");*/

}int judge_vertex(wgraph *w,int i,struct visit *vp)

void create_tlgraph(wgraph *w,algraph *g)

{wgraph t;

int i,j,t,h,k=2;

int m=1; int abc,bcd;

管道鋪設施工的最佳方案問題

管道鋪設施工的最佳方案問題

資料結構管道鋪設施工的最佳方案

地毯鋪設施工方案

管道鋪設施工的最佳方案問題

管道鋪設施工的最佳方案問題

資料結構管道鋪設施工的最佳方案

地毯鋪設施工方案

相關推薦