クラスカル法
概要
クラスカル法はグラフ理論において重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズム。
最小全域木とは、「グラフのすべての頂点を含む木で、辺の重みの総和が最小のもの」をいう。
貪欲法の一種で、最小全域木を求めるほかのアルゴリズムとして、プリム法、逆削除法、ブルーフカ法などがある。
アルゴリズム
- \(T\) を空グラフとする。
- 辺の重みが最小のものから順に取り出す。取り出した辺 \(e\) を加えたグラフ \(T+e\) に閉路ができないならば、\(T \leftarrow T+e\) とし、閉路ができる場合は辺 \(e\) を捨てる。
取り出した辺 \(e\) を加えた \(T+e\) で閉路ができることは、辺 \(e\) の両端が同じ連結成分であることと同値であるため、閉路の判定には Union Find を利用するのがよい。