MST(最小生成樹)

note

。Spanningt Tree(生成樹)

。MST只有一個，可以用以下兩種方法去找

→ Kruskal’s Algo.(link)

→ Prim’s Algo.(link)

。Spanningt Tree

→包含所有點的樹，稱為生成樹

→可能有很多種

→完全連通圖才可能有生成樹

→生成樹的權重為樹上每條邊的總和

。MST

擁有最小權重的生成樹，稱為最小生成樹