圖形演算法-最小生成樹

最小生成樹(Minimum Spanning Tree)

在無向圖有權重的連通圖中找尋可以連接所有點的邊且不形成循環，且這些邊的權重和最小，可以連通所有點且不形成循環，一定會形成樹，這樣的問題稱作最小生成樹(Minimum Spanning Tree)。

本節介紹Kruskal的最小生成樹演算法，因為這個演算法較容易實作，Kruskal演算法由最小的邊出發，找出最小不形成循環的邊，直到邊的個數為點的個數少1，就找到最小生成樹。

使用Kruskal演算法找出最小生成樹

以下圖為例，進行Kruskal演算法的解說。

如何判斷是否選取的邊形成循環？這時需要使用集合的概念，剛開始每一個點都是一個集合，每個集合都只有一個元素，當加入最小生成樹的邊，邊的兩端點節點屬於同一個集合，就會形成循環，該邊不能是最小生成樹的邊。

Step1)將最小邊(3,5)加入最小生成樹，將點3與點5屬於不同的集合，且都是只有一個元素的集合，所以{3}與{5}進行聯集形成一個新集合{3,5}。

Step2)將最小邊(1,2)加入最小生成樹，將點1與點2屬於不同的集合，且都是只有一個元素的集合，所以{1}與{2}進行聯集形成另一個集合{1,2}，目前集合有{3,5}與{1,2}。

Step3)將最小邊(0,2)加入最小生成樹，將點0與點2屬於不同的集合，所以{0}與{1,2}進行聯集形成另一個集合{0,1,2}，目前集合有{3,5}與{0,1,2}。

Step4)將最小邊(0,1)加入最小生成樹，點0與點1都屬於集合{0,1,2}，如果加入邊(0,1)則會形成循環，所以不能加入邊(0,1)，目前集合有{3,5}與{0,1,2}。

Step5)將最小邊(2,3)加入最小生成樹，點2與點3屬於不同的集合，所以{0,1,2}與{3,5}進行聯集形成另一個集合{0,1,2,3,5}，目前集合有{0,1,2,3,5}。

Step6)將最小邊(3,4)加入最小生成樹，點3與點4屬於不同的集合，所以{0,1,2,3,5}與{4}進行聯集形成另一個集合{0,1,2,3,4,5}，目前集合有{0,1,2,3,4,5}，到此完成最小生成樹。

(一)最小生成樹

給定最多100個節點以內的無向圖，每個節點編號由0開始編號，且節點編號皆不相同，每個邊的權重為正整數，相同起點與終點的邊只有一個，請找出最小生成樹的邊權重和。

輸入說明

輸入正整數n與m，表示圖形中有n個點與m個有向邊，接下來有m行，每個邊有三個數字，前兩個數字為邊的兩端點節點編號與最後一個數字為邊的權重，保證節點編號由0到(n-1)。

輸出說明

輸出最小生成樹的邊權重和。

範例輸入

6 9

0 1 6

0 2 5

0 3 11

0 4 16

1 2 3

2 3 7

2 5 10

3 4 9

3 5 2

範例輸出

26

(a)解題想法

將所有邊的節點與權重，輸入到陣列edge，將陣列edge依照w由小到大排序，由小到大依序取出每一個邊，使用陣列parent記錄節點的上一層節點編號，有相同根節點的節點編號，表示同一個集合，若取出最小邊的兩端點，由陣列parent來判斷是否在同一個集合內，若有相同的根節點節點編號，表示同一個集合，加入此邊會形成循環，該邊不是最小生成樹的邊；若有不同的根節點節點編號，表示兩端點不在同一個集合內，加入此邊不會形成循環，該邊是最小生成樹的邊，接著更改陣列parent，集合元素個數越多者要放在上面，這樣由陣列parent往上找根節點才能在較少比較次數內完成，程式會有較佳的效率。

(c)程式結果預覽

按下「執行->編譯並執行」，結果顯示在螢幕如下。

(二)連接圖形所有點的最短距離

給定最多100個節點以內XY平面的點座標，表示一個國家的城市個數，假設要找出連接這些城市的道路，且道路可以取任兩點的直線距離進行建置，道路的成本與道路的距離成正比，請幫這個國家找出讓這些城市可以連接起來的道路最短距離。

輸入說明

輸入正整數n，表示有n個城市，接下來有n行，每一行有兩個數值，表示一個城市所在平面的X與Y座標值，座標值可以是浮點數。

輸出說明

輸出將n個城市連接起來的道路最短距離。

範例輸入

5

0.0 0.0

2.0 2.0

4.0 3.0

5.0 5.0

2.0 5.0

範例輸出

10.129

(a)解題想法

將所有邊的節點與權重，輸入到陣列edge，將陣列edge依照w由小到大排序，由小到大依序取出每一個邊，使用陣列parent記錄節點的上一層節點編號，有相同根節點的節點編號，表示同一個集合，若取出最小邊的兩端點，由陣列parent來判斷是否在同一個集合內，若有相同根節點的節點編號，表示同一個集合，加入此邊會形成循環，該邊不是最小生成樹的邊；若有不同的根節點節點編號，表示兩端點不在同一個集合內，加入此邊不會形成循環，該邊是最小生成樹的邊，最後更改陣列parent，集合元素個數越多者要放在上面，這樣由陣列parent往上找根節點才能在較少比較次數內完成。