プリム法

発電所からケーブルを引くところを想像してください。まず一番近い町をつなぎ、次にすでにつながったどこかに一番近い町をつなぎ、これを続けます。それがプリム法で、最後には必ず最も安いネットワークができます。

1つのノードから木が育つグラフ。周りの待機中のノードの最良のエッジが破線で描かれ、下に待機中のノードが並んでいる
1つのノードから木が育つグラフ。周りの待機中のノードの最良のエッジが破線で描かれ、下に待機中のノードが並んでいる

考え方

最小全域木は、重み付きグラフのすべてのノードを、エッジの長さの合計ができるだけ小さくなるようにつなぎます。プリム法は、スタートから外へ1本の木を育ててこれを作ります。木がばらばらに分かれることはありません。各ステップで、木から出る最短のエッジによって、ちょうど1つの新しいノードが加わります。

ステップごとに

スタートを木に入れます。木の外の各ノードについて、最良のエッジ、つまり木のいずれかのノードへの最短のエッジを持っておきます。そして繰り返します。最良のエッジが最も短い外のノードを選び、そのエッジとともに木に加え、そのノードのエッジを調べます。木の外の隣接ノードがより短いエッジでたどり着けるようになったら、そのエッジが新しい最良のエッジになります。すべてのノードが木に入ったら終わりです。

例

長さ 1 の A–B、2 の B–C、3 の A–C、4 の C–D、5 の B–D というエッジで、A から始めます。A のエッジで B の最良のエッジは 1、C は 3 になります。B が最も近いので A–B で加わり、そのエッジで C は 2 に改善され、D は 5 を得ます。C が B–C で加わり、そのエッジ C–D で D は 4 に改善されます。最後に D が C–D で加わります。木 A–B、B–C、C–D の長さの合計は 1 + 2 + 4 = 7 です。

正しい理由

各ステップで、ノードは木の中と木の外の2つのグループに分かれます。カット性質によれば、このような2つのグループの間の最短のエッジは、必ずいずれかの最小全域木に含まれます。プリム法は常にまさにそのエッジを加えるので、それまでに作った木はいつでも最小全域木に完成させることができ、すべてのノードが加わったとき、それは最小全域木になっています。

歴史と速さ

チェコの数学者ヴォイチェフ・ヤルニーク(Vojtěch Jarník)が1930年にこのアルゴリズムを発表しました。ロバート・プリム(Robert Prim)が1957年にベル研究所(Bell Labs)で再発見し、エドガー・ダイクストラ(Edsger Dijkstra)が1959年にもう一度見つけました。待機中のノードを二分ヒープに入れると、ノード数 V、エッジ数 E に対して計算量は E log V で増えます。単純な配列なら約 V² で、ほぼすべてのノードの組がつながっているときはこちらが有利です。フィボナッチヒープなら E + V log V です。

試してみよう

アプリを開き、ノードをクリックしてそこから始め、「ステップ」を押します。木の中のノードは緑、待機中のノードは青で、各待機中のノードの最良のエッジは破線で描かれます。待機中のノードは最良のエッジの長さとともにグラフの下に短い順に並び、先頭のノードが次に加わります。いろいろなノードから始めて、順序は変わっても長さの合計は変わらないことを確かめてみましょう。

よくある質問

プリム法とダイクストラ法の違いは何ですか?

どちらも優先度付きキューを使ってスタートから領域を広げます。プリム法は待機中のノードを木への最良のエッジ1本の長さで並べ、ダイクストラ法はスタートからの距離全体で並べます。プリム法は最小全域木を、ダイクストラ法は最短経路の木を作ります。

プリム法は負のエッジの長さでも動きますか?

はい。ダイクストラ法と違い、プリム法はエッジどうしを比べるだけなので、負の長さがあっても問題ありません。それでも長さの合計が最小の全域木を見つけます。

グラフが連結でない場合は?

プリム法はたどり着けるノードをすべて加えたところで止まり、スタートを含む部分だけの最小全域木を作ります。まだたどり着いていないノードから再び実行すると、最小全域森が得られます。

プリム法とクラスカル法はどちらがよいですか?

どちらかが常に勝つわけではありません。プリム法は密なグラフや隣接ノードのリストで持つグラフに向き、クラスカル法はエッジのリストで与えられる疎なグラフに向いています。どちらも長さの合計が同じ木を見つけます。

試してみますか?

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

プリム法を試す