クラスカル法
無向連結グラフの
最小全域木
を求めるアルゴリズム
O(E log E)
辺のコストを安い方から閉路を作らないように追加していく
この閉路の判定は
UnionFind
を使うことでほぼ定数時間
辺をコストによってソートするところでO(E log E)
ソート済みもしくは
線形時間ソート
できるならO(E)
最小全域木(クラスカル法とUnionFind) - アルゴリズム講習会
クラスカル法 - Wikipedia