管道鋪設(shè)問(wèn)題

1、實(shí)驗(yàn)三：管道鋪設(shè)施工的最佳方案一問(wèn)題描述1.實(shí)驗(yàn)題目：需要在某個(gè)城市n個(gè)居民小區(qū)之間鋪設(shè)煤氣管道，則在這n個(gè)居民小區(qū)之間只需要鋪設(shè)n1條管道鋪設(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)值形式給出

2、，網(wǎng)的存儲(chǔ)采用鄰接表的結(jié)構(gòu)。3.測(cè)試數(shù)據(jù)：使用下圖給出的無(wú)線網(wǎng)數(shù)據(jù)作為程序的輸入，求出最佳鋪設(shè)方案。ABCDEHGFI98.718.28.732.844.656.421.367.385.679.212.152.510.541.15.9參考解：EdgeTypeinfo權(quán)值structnodenext指向下一個(gè)鄰接點(diǎn)的指針域EdgeNodetypedefstructvnode頂點(diǎn)表節(jié)點(diǎn)vertexTypevertex頂點(diǎn)域EdgeNodef