# 4.3.3 - Sollin's algorithm

Steps:

1. 將各頂點視為獨立的一棵樹
2. 就每棵樹挑出成本最小的邊，並加入此樹
3. 刪除重複挑出的邊，只保留一份
4. 重複2\~3直到只剩一棵樹，或是無邊可挑

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

e.g.

<img src="https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIpnrR8j8h5zSGnE3TX%2F-LIpo1kkcpkN8J3_YPvK%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-01%2015.19.21.jpg?alt=media&#x26;token=1ffb1e86-7633-49b0-91ef-d668e91da314" alt="" data-size="original">&#x20;

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

   (1, 6)

   (2, 7)

   (3, 4)

   ~~(4, 3)~~

   (5, 4)

   ~~(6, 1)~~

   ~~(7, 2)~~

   <img src="https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIsWwey25UTRPJLf89m%2F-LIsXYjDg0t94hwkCM0H%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-02%2010.49.09.jpg?alt=media&#x26;token=72ab8149-979e-4a0d-a58e-9be794e512a2" alt="" data-size="original">&#x20;
2. 從每棵樹中挑出最小的邊

   (6, 5)

   (2, 3)

   ~~(3, 2)~~

   <img src="https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIpnrR8j8h5zSGnE3TX%2F-LIsSi4WwlGei4o4ftvc%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-01%2015.45.52.jpg?alt=media&#x26;token=b058375d-e247-4207-ba9a-160ecba70325" alt="" data-size="original">&#x20;
3. 只剩一棵樹，end