MST

最小成本擴張樹

擴展樹：以最少的邊，連接圖形中的所有頂點。

最小成本擴張樹：在邊加上權重，並將權重作為邊的成本或距離，則稱為網路。而一網路之擴展樹具有最小成本，則稱為最小成本擴展樹(minuimum cost spanning tree)。

均使用「貪婪算法 Greedy Algorithm」

Prim's演算法

基於點的延伸，G = (V, E)，其中集合V = {1, 2, 3......., n}，並設定集合U = {1}，每次都從集合V當中挑選能與集合U形成最小成本邊的頂點，直到所有的點都被加入到集合U。

Kruskal's 演算法

基於邊的選擇，每一次都挑選成本最小的邊，若加入此邊不會使擴展樹形成循環，就將邊加入擴展樹，若會形成循環就略過此邊，並且不將此邊加入擴展樹當中。

Sollin's 演算法

列舉所有頂點的最短邊，並刪除重複的，再將其形成的樹林尋找最小邊串聯。

結論

1. 最小成本擴展樹是用最少（小）的邊形成的

2. Prim's算法以點為主

3. Kruskal's算法以邊為主

4. Sollin's算法是列出所有最小成本邊並刪除相同邊，在串聯起來

5. 無論使用何種算法，皆會得到相同的最小成本擴展樹