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

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

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

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