KruskalとPrim
どちらもMinimum Spanning Treeを求めるGreedy Algorithmであるが,いつもどっちがどっちだったか忘れてしまうのでメモ.
点数をn,辺数をmとする.
Kruskal
- 辺を軽い順に追加していくもの
- 木マトロイド
- 普通の実装だとO(mn),Union Findを使えばO(m α(m,n))
Prim
- 1点からどんどん伸ばしていく
- 根付き森グリードイド
- 普通の実装だとO(n^2),Fibonacci Heapを使えばO(m+n log n),頑張ればO(m α(m,n))らしい(Chazelle[2000]:A minimum spanning tree algorithm with inverse-Ackermann type complexity.,あとで調べる)