2010-04-07から1日間の記事一覧

KruskalとPrim

どちらもMinimum Spanning Treeを求めるGreedy Algorithmであるが,いつもどっちがどっちだったか忘れてしまうのでメモ. 点数をn,辺数をmとする. Kruskal 辺を軽い順に追加していくもの 木マトロイド 普通の実装だとO(mn),Union Findを使えばO(m α(m,n))…