4.3.3 - Sollin's algorithm

Steps:

1. 將各頂點視為獨立的一棵樹

2. 就每棵樹挑出成本最小的邊，並加入此樹

3. 刪除重複挑出的邊，只保留一份

4. 重複2~3直到只剩一棵樹，或是無邊可挑

若 $S$的邊數小於 $v-1$ ，則 $G$ 無spanning tree。

e.g.

1. 從每棵樹中挑出最小的邊

   (1, 6)

   (2, 7)

   (3, 4)

   (4, 3)

   (5, 4)

   (6, 1)

   (7, 2)

   

2. 從每棵樹中挑出最小的邊

   (6, 5)

   (2, 3)

   (3, 2)

   

3. 只剩一棵樹，end