- 現在
- 木に含まれる
- 木に隣接
- 現時点の最良エッジ
プリム法
プリム法は、すべてのノードをつなぐ最も安いエッジの集まりである最小全域木を、スタートから1本の木を育てて作ります。各ステップで、木から最短のエッジでたどり着けるノードを加えます。ノードをクリックしてそこから始め、ステップを進めて、待機中のノード、その最良のエッジ、木が育つ様子を見てみましょう。 「再生」で木が育つ様子を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。ノードをクリックするとスタートになり、木はそこから育ちます。各エッジの数字はその長さです。グラフの下には木に加わるのを待つノードが並び、それぞれ木への最良のエッジの長さが表示されます。最良のエッジは破線で描かれます。「新しいグラフ」で別のグラフを作ります。ノード数とエッジ数を選べます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- ノードをクリックしてスタートにします。木はそこから育ちます。
- 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。
- グラフの下の待機中のノードと、それぞれの木への最良のエッジを見てみましょう。「新しいグラフ」で別のグラフを試せます。
プリム法のしくみ
1つのノードだけの木から始めます。木の外の各ノードは、木への最短のエッジがあればそれを覚えておきます。エッジが最も短いノードを取り、そのノードとエッジを木に加えて、そのノードのエッジを調べることを繰り返します。あるエッジが隣接ノードのこれまでの最良のエッジより短ければ、それがその隣接ノードの最良のエッジになります。すべてのノードが加わると、木のエッジ数はノード数より1少なく、長さの合計はできるだけ小さくなっています。
プリム法とダイクストラ法
プリム法とダイクストラ法はほとんど同じに見えます。どちらもスタートから領域を広げ、待機中のノードを優先度付きキューに入れます。違いはキューの中の数値です。ダイクストラ法は各ノードのスタートからの距離全体を持ち、プリム法は木への最良のエッジ1本の長さだけを持ちます。そのためダイクストラ法は最短経路の木を、プリム法は長さの合計が最小の木を作り、2つの木はしばしば異なります。
よくある質問
プリム法とは何ですか?
重み付きグラフの最小全域木を作る貪欲法です。スタートのノードから1本の木を育て、木と木の外のノードをつなぐ最短のエッジを常に加えます。
スタートのノードは結果に影響しますか?
影響するのは順序だけです。どのスタートからでも、プリム法は長さの合計が同じく最小の全域木で終わります。長さの等しいエッジがあると、木そのものは変わることがあります。
プリム法を考えたのは誰ですか?
1930年にヴォイチェフ・ヤルニーク(Vojtěch Jarník)が最初に示しました。1957年にロバート・プリム(Robert Prim)、1959年にエドガー・ダイクストラ(Edsger Dijkstra)が再発見したため、ヤルニーク法やプリム–ヤルニーク法とも呼ばれます。
プリム法はどのくらい速いですか?
二分ヒープを使うと、ノード数 V、エッジ数 E に対して計算量は E log V で増えます。ヒープの代わりに単純な配列を使うと約 V² ステップかかり、ほぼすべてのノードの組がつながった密なグラフではこちらが有利です。
グラフはどこかに送信されますか?
いいえ。グラフの作成と木の構築はブラウザ内で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ