最小生成樹

泥濘城市問題

很久以前有個沒有鋪設道路的城市，每次暴雨後城市會變得很泥濘難走，甚至車子也會卡在泥巴中。市長決定將某些街道鋪上石板，可是又不能花不必要的錢。

市長指定了兩個條件：

1. 鋪設的石板路可讓人們從自己家到任何人家。
2. 鋪路的花費越少越好。

以下是城市平面圖，每棟房子間的石板代表鋪設那條路的花費，你可以幫忙市長解決這個問題嗎？

答：最少要鋪設_________條石板路，花費____________個石板？

你可以歸納出如何解決這個問題的方法嗎？

日常生活上在很多地方都是遇到這種問題，例如電力、瓦斯、水、光纖網路要怎麼連結到新的社區及每棟房子，這是電力、水力或固網公司必須好好研究的問題，如何設計總長度最小的網路，又被稱為「最小生成樹（Minimal Spanning Tree）」。

城市中有n個房子需要多少路呢？

最佳答案是n-1條路（連結）。

最小生成樹不只對電力、水管、網路有用，也可幫助我們解決輸油管、航線問題。

如何解決最小生成樹問題？

J. B. Kruskal 1956年提出Kruskal演算法：

1. 從沒有任何連結的空白開始
2. 依他們的大小升冪順序加入
3. 只能把那些先前還沒連結的節點加入連結中

再試看看下面這題的最佳解答是什麼？

簡易表示方式：房子用圓代表節點，泥濘道路用線表示，鋪路的成本用數字寫在線邊。

解答：

第一題：9 / 23

第二題：9 / 25