MST
Minimum Spanning Trees
Minimum Spanning Trees
最小成本擴張樹
擴展樹:以最少的邊,連接圖形中的所有頂點。
最小成本擴張樹:在邊加上權重,並將權重作為邊的成本或距離,則稱為網路。而一網路之擴展樹具有最小成本,則稱為最小成本擴展樹(minuimum cost spanning tree)。
均使用「貪婪算法 Greedy Algorithm」
基於點的延伸,G = (V, E),其中集合V = {1, 2, 3......., n},並設定集合U = {1},每次都從集合V當中挑選能與集合U形成最小成本邊的頂點,直到所有的點都被加入到集合U。
基於邊的選擇,每一次都挑選成本最小的邊,若加入此邊不會使擴展樹形成循環,就將邊加入擴展樹,若會形成循環就略過此邊,並且不將此邊加入擴展樹當中。
列舉所有頂點的最短邊,並刪除重複的,再將其形成的樹林尋找最小邊串聯。
最小成本擴展樹是用最少(小)的邊形成的
Prim's算法以點為主
Kruskal's算法以邊為主
Sollin's算法是列出所有最小成本邊並刪除相同邊,在串聯起來
無論使用何種算法,皆會得到相同的最小成本擴展樹