クラスカル法

エッジを並べ替え、短いものから取り、決してループを作らない。クラスカル法はおそらく最も単純な貪欲法ですが、グラフのすべてのノードをつなぐ最も安い方法を必ず見つけます。

木のいくつかの部分が同時に育つグラフ。閉路を作るため飛ばされたエッジが赤い破線で描かれ、下にまだ試していないエッジが並んでいる
木のいくつかの部分が同時に育つグラフ。閉路を作るため飛ばされたエッジが赤い破線で描かれ、下にまだ試していないエッジが並んでいる

考え方

最小全域木は、重み付きグラフのすべてのノードを、エッジの長さの合計ができるだけ小さくなるようにつなぎます。クラスカル法はスタートから1本の木を育てるのではありません。グラフ全体を一度に見て、どのノードもそれだけで1つの部分という状態から始め、使える最短のエッジで部分をつなぎ続け、部分が1つだけになるまで続けます。

ステップごとに

エッジを短い順に並べ、その順に試します。エッジの両端が異なる部分にあれば、木に加えます。2つの部分は1つになります。両端がすでに同じ部分にあれば、そのエッジは閉路を作るので飛ばします。ノードが n 個なら、木は n − 1 本のエッジで完成し、残りのエッジは見る必要がありません。

例

長さ 1 の A–B、2 の B–C、3 の A–C、4 の C–D、5 の B–D というエッジを考えます。クラスカル法は A–B を加え、次に B–C を加えて C を部分 A–B につなぎます。次は A–C ですが、A と C はすでに同じ部分にあるので、閉路 A–B–C を作ることになり、飛ばします。C–D で D が加わり、4つのノードすべてが3本のエッジの木になり、長さの合計は 7 です。最も長いエッジ B–D は試されもしません。

Union-Find

クラスカル法が問う難しい質問は1つだけです。この2つのノードはすでに同じ部分にあるか? Union-Find 構造がこれに答えます。各部分は、代表を指すリンクでできた小さな木です。find はリンクをたどって代表を見つけ、union は一方の代表をもう一方の下につなぎます。たどったノードをすべて代表に直接向ける経路圧縮と、サイズによる併合によって、リンクはとても短く保たれ、1回の問い合わせはほぼ定数時間になります。

歴史と速さ

ジョゼフ・クラスカル(Joseph Kruskal)は1956年、Proceedings of the American Mathematical Society の短い論文でこのアルゴリズムを発表しました。最も遅いのはエッジの並べ替えなので、エッジ数 E に対して計算量は E log E で増えます。エッジがすでに並んでいるか、長さが小さな整数なら、ほぼ線形です。

試してみよう

アプリを開いて「ステップ」を押します。まだ試していないエッジがグラフの下に短い順に並びます。2つの部分をつなぐエッジは緑になり、閉路を作るエッジは赤い破線で描かれます。グラフのあちこちで小さな部分が育ってまとまる様子を見て、最後のほうのエッジがしばしば一度も試されないことに注目してください。

よくある質問

クラスカル法はなぜエッジを並べ替えるのですか?

加えるエッジがどれも、まだ2つの部分をつなぐ最短のエッジになるようにするためです。この貪欲な選択はカット性質により常に安全で、飛ばすエッジはどれも、それが作る閉路の中で最も長いので、決して必要ありません。

素集合データ構造とは何ですか?

Union-Find の別名です。互いに重ならない集合の集まり(ここでは育っていく森の各部分)を管理し、要素がどの集合に属するかを調べたり、2つの集合をすばやく併合したりできます。

クラスカル法は連結でないグラフでも動きますか?

はい。つながっていない部分をつなげるエッジはないので、グラフの連結な部分ごとに1本ずつ木ができ、最小全域森で終わります。

クラスカル法はほかに何に使われますか?

最後の部分がまとまる前に早めに止めると、ノードがクラスタに分かれます。これが単連結法(single-linkage clustering)です。エッジの長さをランダムにした格子で実行すると迷路ができます。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

クラスカル法を試す