【メモ】最小全域木の探索

競技プログラミング メモ

最小全域木の探索について

アルゴリズム

ナイーブな実装だと計算量が O(N^3) 程度。ノード数が多いグラフでは計算量をいかに落とすかがポイントっぽい。

プリム法

グラフ G(V,E) の頂点全体の集合を V 最小全域木(MST)に属する頂点の集合を T とする。

  1. G から任意の頂点 a を選び、それをMSTのルートとして T に追加

  2. T が空になるまで以下の処理をループ 2-1.「 V の要素から T の要素をつなぐエッジのうち、最小コストを持つエッジ e を探す 2-2. V = {V} + {eのT側の要素} 、T = {T} - {eのT側の要素} とする 2-3.エッジのコストの総和に e のコストを追加する

クラスカル法

あとで書く

参考

問題

最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge

D - Built?