プリム法

プリム法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。全域木のうち、その辺群の重みの総和が最小となる木を求めるものである。このアルゴリズムは1930年に数学者 Vojtěch Jarník が発見し、1957年に計算機科学者ロバート・C・プリムが独自に発見、さらに1959年にはエドガー・ダイクストラが再発見しダイクストラ法の論文に記載している。そのため、DJP法、Jarník法、Prim-Jarník法などとも呼ばれることがある。アルゴリズムの発想や計算量は同時期に発表されたダイクストラ法に類似している。

1. アルゴリズムの解説
------------

このアルゴリズムでは1つの辺から始めて、全頂点を覆うようになるまで連続的に木の大きさを拡大していく。

入力: 重み付きグラフ
出力: Vnew と Enew が最小全域木を表している。Vnew = {x}、ここで x は V の元であり、任意のノード Enew = {}

while  Vnew に含まれる頂点 u と 含まれない頂点 v を結ぶ重みが最小の辺  を E から選択 v を Vnew に加える  を Enew に加える

2. 計算量
------

V は頂点の数、E は辺の数。「重みが最小の辺」をどのように探索するかで計算量が変わる。

グラフを隣接行列で表した単純な実装で、重みの配列を探索して重みが最小の辺を求める場合、 の時間がかかる。単純な二分ヒープと隣接リストを使うと、 の時間がかかる。より洗練されたフィボナッチヒープを使うと、E が の程度まで稠密であれば、時間は とかなり改善される。

3. 例
----



4. 擬似コード
--------

4.1. Min-heap
-------------

初期化//入力: グラフ graph、辺の重みを返す関数 weight-function、初期頂点 initial vertex//
全頂点をまだ見ていない状態に初期化し、initial vertex を木に追加し、最小グラフから最小距離を除去することを考慮して全ての頂点を min-heap Q に置く。for each //vertex// in //graph//set min_distance of //vertex// to ∞set parent of //vertex// to //null//set minimum_adjacency_list of //vertex// to empty listset is_in_Q of //vertex// to trueset distance of initial vertex to //zero// add to minimum-heap Q all vertices in graph.アルゴリズム上の初期化アルゴリズムで、次の状態になっている。
//nearest vertex// とは Q[0] にあり、これが最新の追加である。
//fringe// とは Q 上の v であり、最も近い頂点を除去した後で v の距離が ∞ より小さいもの。
//not seen// とは Q 上の v であり、最も近い頂点を除去した後で v の距離が ∞ であるもの。このwhileループは、remove minimum がヌルを返すと終了する。隣接リストは有向グラフを返せるように設定する。
while //latest_addition// = remove minimum in Qset is_in_Q of //latest_addition// to false add //latest_addition// to ) add  to for each //adjacent// of //latest_addition//if  and  < min_distance of //adjacent//)set parent of //adjacent// to //latest_addition//set min_distance of //adjacent// to weight-function update //adjacent// in Q, order by min_distance

5. 正しさの証明
---------

//P// を重み付き連結グラフとする。プリム法の繰り返しでは、毎回ある部分グラフからその外部へと接続している辺を探し出す。//P// は連結グラフなので、全ての頂点に常に道が存在する。プリム法の出力 //Y// に追加される辺と頂点はつねに接合しているため、//Y// は木である。//Y1// が P の最小全域木であるとする。//Y1//=//Y// なら、//Y// は最小全域木である。そうでない場合、//Y// にあって //Y1// にない辺のうち、//Y// の構築時に最初に追加された辺を //e// とし、//e// が追加される以前に追加された辺に接合している頂点の集合を //V// とする。//e// の端点の一方は //V// にあり、もう一方はそうではない。//Y1// は //P// の全域木なので、//Y1// にはその2つの端点をつなぐ道がある。その道をたどると、//V// 内の頂点から //V// 外の頂点への辺 //f// に必ず遭遇する。さて、//Y// に //e// を追加した時の繰り返しにおいて、//e// よりも //f// の方が重みが小さければ //f// が追加されていただろう。しかし //f// は追加されなかったので、次の結論が得られる。

//Y1// から //f// を除いて //e// を追加したグラフを //Y2// とする。//Y2// が連結グラフであり、//Y1// と同数の辺を持ち、辺の重みの総和が //Y1// より小さいことは容易に示すことができる。従って、これも //P// の最小全域木であり、//e// を含み、それ以前に //V// の構築の際に追加された全ての辺を含んでいる。以上を繰り返し適用していくと、//Y// と全く同じ //P// の最小全域木を得られる。以上から、//Y// は最小全域木であることがわかる。

最小全域木問題の他のアルゴリズムとしてクラスカル法やブルーフカ法がある。

6. 参考文献
-------

V. Jarník: //O jistém problému minimálním// [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57-63. 
R. C. Prim: //Shortest connection networks and some generalisations//. In: //Bell System Technical Journal//, 36 , pp. 1389–1401
Dijkstra, E.W. . [1]. In //Numerische Mathematik//, 1 , S. 269 ～ 271.
D. Cherition and R. E. Tarjan: //Finding minimum spanning trees//. In: //SIAM Journal of Computing//, 5 , pp. 724–741
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. //Introduction to Algorithms//, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.

7. 外部リンク
--------

[2]
[3] at cut-the-knot
[4]
[5] Java アプレット