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

  • 現在
  • 木に含まれる
  • 木に隣接
  • 現時点の最良エッジ

プリム法についてもっと見る

プリム法

プリム法は、すべてのノードをつなぐ最も安いエッジの集まりである最小全域木を、スタートから1本の木を育てて作ります。各ステップで、木から最短のエッジでたどり着けるノードを加えます。ノードをクリックしてそこから始め、ステップを進めて、待機中のノード、その最良のエッジ、木が育つ様子を見てみましょう。 「再生」で木が育つ様子を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。ノードをクリックするとスタートになり、木はそこから育ちます。各エッジの数字はその長さです。グラフの下には木に加わるのを待つノードが並び、それぞれ木への最良のエッジの長さが表示されます。最良のエッジは破線で描かれます。「新しいグラフ」で別のグラフを作ります。ノード数とエッジ数を選べます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。

使い方

  1. ノードをクリックしてスタートにします。木はそこから育ちます。
  2. 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。
  3. グラフの下の待機中のノードと、それぞれの木への最良のエッジを見てみましょう。「新しいグラフ」で別のグラフを試せます。

プリム法のしくみ

1つのノードだけの木から始めます。木の外の各ノードは、木への最短のエッジがあればそれを覚えておきます。エッジが最も短いノードを取り、そのノードとエッジを木に加えて、そのノードのエッジを調べることを繰り返します。あるエッジが隣接ノードのこれまでの最良のエッジより短ければ、それがその隣接ノードの最良のエッジになります。すべてのノードが加わると、木のエッジ数はノード数より1少なく、長さの合計はできるだけ小さくなっています。

プリム法とダイクストラ法

プリム法とダイクストラ法はほとんど同じに見えます。どちらもスタートから領域を広げ、待機中のノードを優先度付きキューに入れます。違いはキューの中の数値です。ダイクストラ法は各ノードのスタートからの距離全体を持ち、プリム法は木への最良のエッジ1本の長さだけを持ちます。そのためダイクストラ法は最短経路の木を、プリム法は長さの合計が最小の木を作り、2つの木はしばしば異なります。

よくある質問

プリム法とは何ですか?

重み付きグラフの最小全域木を作る貪欲法です。スタートのノードから1本の木を育て、木と木の外のノードをつなぐ最短のエッジを常に加えます。

スタートのノードは結果に影響しますか?

影響するのは順序だけです。どのスタートからでも、プリム法は長さの合計が同じく最小の全域木で終わります。長さの等しいエッジがあると、木そのものは変わることがあります。

プリム法を考えたのは誰ですか?

1930年にヴォイチェフ・ヤルニーク(Vojtěch Jarník)が最初に示しました。1957年にロバート・プリム(Robert Prim)、1959年にエドガー・ダイクストラ(Edsger Dijkstra)が再発見したため、ヤルニーク法やプリム–ヤルニーク法とも呼ばれます。

プリム法はどのくらい速いですか?

二分ヒープを使うと、ノード数 V、エッジ数 E に対して計算量は E log V で増えます。ヒープの代わりに単純な配列を使うと約 V² ステップかかり、ほぼすべてのノードの組がつながった密なグラフではこちらが有利です。

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

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

試してみますか?

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

エディターへ