読者です 読者をやめる 読者になる 読者になる

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.,あとで調べる)