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

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

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

3、來(lái)存儲(chǔ)圖，因此需要圖這個(gè)抽象數(shù)據(jù)類型。1.圖抽象數(shù)據(jù)類型定義：圖抽象數(shù)據(jù)類型定義：ADTALGraph數(shù)據(jù)對(duì)象：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)；