管道鋪設(shè)問題

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

2、，網(wǎng)的存儲采用鄰接表的結(jié)構(gòu)。3.測試數(shù)據(jù)：使用下圖給出的無線網(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指向下一個鄰接點的指針域EdgeNodetypedefstructvnode頂點表節(jié)點vertexTypevertex頂點域EdgeNodef