- 現在
- 木に含まれる
- 閉路ができる
クラスカル法
クラスカル法は、すべてのノードをつなぐ最も安いエッジの集まりである最小全域木を、考えうる最も単純な方法で作ります。エッジを短い順に取り、閉路を作らない限りそれを残すだけです。ステップを進めて、別々の部分が育って1本の木にまとまる様子と、飛ばされるエッジを見てみましょう。 「再生」で木が育つ様子を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。各エッジの数字はその長さです。グラフの下には、まだ試していないエッジが短い順に並びます。両端がすでにつながっているエッジは閉路を作るので、赤い破線で描かれます。「新しいグラフ」で別のグラフを作ります。ノード数とエッジ数を選べます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。
- ステップスライダーをドラッグすると好きな位置に移動できます。まだ試していないエッジがグラフの下に短い順に並びます。
- 赤い破線のエッジに注目しましょう。それらは閉路を作ります。「新しいグラフ」で別のグラフを試せます。
クラスカル法のしくみ
すべてのエッジを短い順に並べます。最初はどのノードもそれだけで1つの部分です。エッジを順に試します。エッジが2つの異なる部分をつなぐなら、それを木に加え、2つの部分は1つになります。両端がすでに同じ部分にあれば、閉路を作るので飛ばします。すべてが1つの部分になったら止まります。それはノード数より1少ないエッジを加えたときで、多くの場合、最後のエッジを試すよりずっと前です。
Union-Find
クラスカル法は、エッジごとに両端がすでにつながっているかを確かめる必要があります。Union-Find 構造はこれにすばやく答えます。各部分には代表のノードが1つあり、find はリンクをたどって代表を見つけ、union は一方の代表をもう一方につなぎます。経路圧縮とサイズによる併合という2つの簡単な工夫で、1回の問い合わせはほぼ定数時間になるので、最も遅いのはエッジの並べ替えで、計算量は E log E で増えます。
よくある質問
クラスカル法とは何ですか?
すべてのエッジを短い順に並べ、すでに選んだエッジと閉路を作らないエッジを1本ずつ加えて最小全域木を作る貪欲法です。
クラスカル法はどうやって閉路を見つけますか?
エッジが閉路を作るのは、両端がすでに選んだエッジでつながっているときだけです。Union-Find 構造はどのノードがつながっているかを管理し、この問いにほぼ一瞬で答えます。
クラスカル法はなぜ正しいのですか?
閉路性質のおかげです。どの閉路でも最も長いエッジは、最小全域木には決して必要ありません。クラスカル法が飛ばすエッジは、それより前のエッジがすべて短いか等しいので、それが作る閉路の中で最も長いエッジです。
プリム法ではなくクラスカル法を使うのはどんなときですか?
クラスカル法は単純で、疎なグラフで速く、エッジの単純なリストに直接使えます。プリム法は密なグラフや隣接リストで持つグラフに向いています。どちらも長さの合計が同じ木を見つけます。
グラフはどこかに送信されますか?
いいえ。グラフの作成と木の構築はブラウザ内で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ