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.，あとで調べる）