管道鋪設(shè)施工的最佳方案問題

1、11問題描述：問題描述：1.實(shí)驗(yàn)題目：實(shí)驗(yàn)題目：需要在某個城市n個居民小區(qū)之間鋪設(shè)煤氣管道，則在這n個居民小區(qū)之間只需要鋪設(shè)n1條管道即可。假設(shè)任意兩個小區(qū)之間都可以鋪設(shè)管道，但由于地理環(huán)境不同，所需要的費(fèi)用也不盡相同。選擇最優(yōu)的方案能使總投資盡可能小，這個問題即為求無向網(wǎng)的最小生成樹。2.基本要求：基本要求：在可能假設(shè)的m條管道中，選取n1條管道，使得既能連通n個小區(qū)，又能使總投資最小。每條管道的費(fèi)用以網(wǎng)中該邊的權(quán)值形式給出，網(wǎng)的存儲

2、采用鄰接表的結(jié)構(gòu)。3.測試數(shù)據(jù)：測試數(shù)據(jù)：使用下圖給出的無線網(wǎng)數(shù)據(jù)作為程序的輸入，求出最佳鋪設(shè)方案。右側(cè)是給出的參考解。4.4.簡述每一部分的對象、目的和要求：簡述每一部分的對象、目的和要求：I.主函數(shù)部分：對象：圖G；目的：為圖G分配空間，以作為后續(xù)調(diào)用函數(shù)的參數(shù)；3用戶輸入字母時，輸入大寫或小寫，都可以被該程序識別，正常運(yùn)行。但必須根據(jù)提示信息后面給出的參考形式，有針對性地輸入逗號。3概要設(shè)計(jì)概要設(shè)計(jì)為了實(shí)現(xiàn)上述功能，該程序以鄰接表

3、來存儲圖，因此需要圖這個抽象數(shù)據(jù)類型。1.圖抽象數(shù)據(jù)類型定義：圖抽象數(shù)據(jù)類型定義：ADTALGraph數(shù)據(jù)對象：D=??iibAdjList|aiiiacbintint?ic，i=123....nn0?數(shù)據(jù)關(guān)系：R=?基本操作：Create_ALGraph(G)；創(chuàng)建圖Create_WLGraph(G)；將圖G中各頂點(diǎn)以及權(quán)值存放到新圖中，權(quán)值只存放一次_info(WG)；將新圖W中的權(quán)值按升序排列Create_TLGraph(wG)；