クラスカル法

プリム法と同様に、重み付き無向グラフにおいて最小全域木を求めるアルゴリズムである。

クラスカル法とは

以下のアルゴリズムである。

1. 辺集合Eを重みの小さな順にsortする。
2. その辺を追加しても閉路ができないのであれば、その辺を答えに追加する。この閉路判定はunion-findなどを使えばより簡単に求めることができる。

証明

これによってできる木はプリム法で構成される木と同じであることが明らか。（暇がある時に追記します）

実装

やってないです。union-findを作ってから書きます。arc076-dとか。