木のエッジ
長さの合計
調べたエッジ

  • 現在
  • 木に含まれる
  • 木に隣接
  • 現時点の最良エッジ
  • 閉路ができる

最小全域木についてもっと詳しく

最小全域木

すべての町をケーブルで、すべての家を水道管で、あるいはネットワーク内のすべてのコンピューターを、できるだけ少ない材料でつなぎたいとします。その答えが最小全域木です。すべてのノードを最小の長さの合計でつなぐエッジの集まりです。クラスカル法かプリム法を選び、1ステップずつ進めて、使える最短のエッジが1本ずつ加わって木が育つ様子を見てみましょう。 「再生」で木が育つ様子を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。アルゴリズムを選びます。クラスカル法はエッジを短い順に試し、プリム法はスタートから1本の木を育てます。ノードをクリックするとプリム法のスタートになります。各エッジの数字はその長さです。グラフの下には、まだ試していないエッジ、または木に加わるのを待つノードと、木への最良のエッジの長さが並びます。「新しいグラフ」で別のグラフを作ります。ノード数とエッジ数を選べます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。

使い方

  1. クラスカル法かプリム法を選びます。プリム法では、ノードをクリックしてスタートにします。
  2. 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。
  3. エッジが木に加わり、長さの合計が増えていく様子に注目しましょう。「新しいグラフ」で別のグラフを試せます。

クラスカル法

すべてのエッジを短い順に並べ、その順に試します。まだつながっていない2つの部分をつなぐエッジなら、木に加えます。両端がすでに木を通じてつながっていれば、閉路ができるので飛ばします。木のエッジ数がノード数より1少なくなったら終わりです。2つのノードがすでにつながっているかをすばやく判定するため、クラスカル法は部分を Union-Find 構造で管理します。

プリム法

1つのノードだけの木から始めます。木の外の各ノードは、木への最短のエッジを覚えておきます。そのエッジが最も短いノードをエッジごと木に加え、そのノードのエッジを調べる、を繰り返します。隣接ノードに、木へのもっと短い入り口が見つかるかもしれません。プリム法はダイクストラ法に似ていますが、比べるのはスタートからの距離全体ではなく、1本1本のエッジです。どちらのアルゴリズムも必ず同じ長さの合計で終わります。

よくある質問

最小全域木とは何ですか?

エッジに長さがある連結グラフで、閉路を作らずにすべてのノードをつなぐエッジの集まりが全域木です。ノードが n 個なら、エッジは必ず n − 1 本です。最小全域木は、長さの合計ができるだけ小さい全域木です。

クラスカル法とプリム法の違いは何ですか?

クラスカル法はグラフ全体のエッジを短い順に見て、別々の部分を1本の木にまとめます。プリム法はスタートから1本の木を育て、木から出る最短のエッジを常に加えます。どちらも貪欲法で、長さの合計が同じ木を見つけます。クラスカル法は疎なグラフに、プリム法は密なグラフに向いています。

最小全域木は1つに決まりますか?

エッジの長さがすべて異なれば、決まります。同じ長さがあると、最小の合計が同じ木が複数ありえて、同点の扱い方によってアルゴリズムが別々の木を選ぶことがあります。

最小全域木は最短経路と同じですか?

いいえ。最小全域木はすべてのエッジの長さの合計を小さくしますが、木の中の2つのノード間の経路は、最短経路よりずっと長くなることがあります。最短経路にはダイクストラ法を使いましょう。

グラフはどこかに送信されますか?

いいえ。グラフの作成と木の構築はブラウザ内で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。

試してみますか?

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

エディターへ