MST(最小生成樹) | KAIDLOG

Loading [MathJax]/extensions/MathZoom.js

2019May27

0

MST(最小生成樹)

note

。Spanningt Tree(生成樹)

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

→ Kruskal’s Algo.(link)

→ Prim’s Algo.(link)

。Spanningt Tree

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

→可能有很多種

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

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

。MST

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

KAIDLOG

ずっと、俺が捨てられた人　