プリム法のソースを表示

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

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

* 入力: 重み付きグラフ（頂点集合 V、辺集合 E）
* 出力: V<sub>new</sub> と E<sub>new</sub> が最小全域木を表している。

 V<sub>new</sub> = {x}、ここで x は V の元であり、任意のノード（出発点）
 E<sub>new</sub> = {}
 
 while (V<sub>new</sub> ≠ V)
     V<sub>new</sub> に含まれる頂点 u と 含まれない頂点 v を結ぶ重みが最小の辺 (u, v) を E から選択（同じ重みの辺が複数あるときは、どちらを選んでも良い）
     v を V<sub>new</sub> に加える
     (u, v) を E<sub>new</sub> に加える

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

{| class="wikitable"
! 使用するデータ構造 !! 計算量
|-
| 単純な集合探索と[[隣接行列]] || <math>O(V^2)</math>
|-
| [[優先度付きキュー]]（[[二分ヒープ]]）と[[隣接リスト]] || <math>O((V + E) \log V) = O(E \log V)</math>
|-
| [[優先度付きキュー]]（[[フィボナッチヒープ]]）と[[隣接リスト]] || <math>O(E + V \log V)</math>
|}

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

== 例 ==

{| border="1" cellspacing="2" cellpadding="5" class="wikitable" style="background:white;"
! イメージ !! 説明
|-
|[[ファイル:Prim_Algorithm_0.svg|200px]]
|グラフの初期状態。辺のそばにある数は重み（距離）を表す。
|-
|[[ファイル:Prim_Algorithm_1.svg|200px]]
|頂点 '''D''' を出発点として選ぶ（任意）。頂点 '''D''' と1つの辺で接続している頂点は '''A'''、'''B'''、'''E'''、'''F''' である。'''A''' が '''D''' に最も近いので、辺 '''AD''' と共に次の頂点として選択する。
|-
|[[ファイル:Prim_Algorithm_2.svg|200px]]
|次に '''D''' または '''A''' に最も近い頂点を選ぶ。'''B''' は '''D''' からは9で '''A''' からは7離れている。'''E'''は15、'''F'''は6である。従って '''F''' が最も近いので、頂点 '''F''' と辺 '''DF''' を選ぶ。
|-
|[[ファイル:Prim Algorithm 3.svg|200px]]
|同様に、'''A''' から7だけ離れている '''B''' を選ぶ。
|-
|[[ファイル:Prim Algorithm 4.svg|200px]]
|残る頂点は '''C'''、'''E'''、'''G''' である。'''C''' は '''B''' から8離れており、'''E''' は '''B''' から7離れており、'''G''' は '''F''' から11離れている。'''E''' が最も近いので、頂点 '''E''' と辺 '''EB''' を選ぶ。
|-
|[[ファイル:Prim Algorithm 5.svg|200px]]
|残る頂点は '''C''' と '''G''' だけである。'''C''' は '''E''' から5離れており、'''G''' は '''E''' から9離れている。従って '''C''' を選び、同時に辺 '''EC''' を選ぶ。
|-
|[[ファイル:Prim Algorithm 6.svg|200px]]
|頂点 '''G''' だけが残っている。'''F''' からは11離れていて、'''E''' からは9離れている。'''E''' の方が近いので、辺 '''EG''' を選ぶ。
|-
|[[ファイル:Prim Algorithm 7.svg|200px]]
|以上で全頂点の選択が終了し、最小[[全域木]]を緑色で示している。この場合の重みの総和は39である。
|}

== 擬似コード ==

=== Min-heap ===
<dl>
<dt>初期化<dt>
<dd>''入力: グラフ graph、辺の重みを返す関数 weight-function、初期頂点 initial vertex''<br />
全頂点をまだ見ていない状態に初期化し、initial vertex を木に追加し、最小グラフから最小距離を除去することを考慮して全ての頂点を min-heap '''Q''' に置く。
{{Indent| }}
 '''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 list
    '''set''' is_in_Q '''of''' ''vertex'' '''to''' true
 '''set''' distance '''of''' initial vertex '''to''' ''zero''
 add to minimum-heap '''Q''' all vertices in graph.
</dd>
<dt>アルゴリズム</dt>
<dd>上の初期化アルゴリズムで、次の状態になっている。
*''nearest vertex'' とは Q[0] にあり、これが最新の追加である。
*''fringe'' とは Q 上の v であり、最も近い頂点を除去した後で v の距離が ∞ より小さいもの。
*''not seen'' とは Q 上の v であり、最も近い頂点を除去した後で v の距離が ∞ であるもの。
このwhileループは、remove minimum が[[null|ヌル]]を返すと終了する。隣接リストは有向グラフを返せるように設定する。<br />
{{Indent|''時間計算量: ループについては V、remove 関数については log(V)''}}
 '''while''' ''latest_addition'' = remove minimum in '''Q'''
     '''set''' is_in_Q '''of''' ''latest_addition'' to false
     add ''latest_addition'' to (minimum_adjacency_list of (parent of ''latest_addition''))
     add (parent of ''latest_addition'') to (minimum_adjacency_list of ''latest_addition'')
{{Indent|''時間計算量: E/V、平均頂点数''}}
     '''for each''' ''adjacent'' '''of''' ''latest_addition''
     '''if''' (is_in_Q of ''adjacent'') and (weight-function(''latest_addition'', ''adjacent'') < min_distance of ''adjacent'')
         '''set''' parent '''of''' ''adjacent'' '''to''' ''latest_addition''
         '''set''' min_distance '''of''' ''adjacent'' '''to''' weight-function(''latest_addition'', ''adjacent'')
{{Indent|''時間計算量: log(V)、ヒープの深さ''}}
         update ''adjacent'' in '''Q''', order by min_distance
</dd>
</dl>

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

{{Indent|''w''(''f'') ≥ ''w''(''e'')}}

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

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

== 参考文献 ==
* 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. (in Czech)
* R. C. Prim: ''Shortest connection networks and some generalisations''. In: ''Bell System Technical Journal'', 36 (1957), pp. 1389–1401
* Dijkstra, E.W. (1959). [http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf ''A note on two problems in connexion with graphs'']. In ''Numerische Mathematik'', 1 (1959), S. 269 ～ 271.
* D. Cherition and [[ロバート・タージャン|R. E. Tarjan]]: ''Finding minimum spanning trees''. In: ''SIAM Journal of Computing'', 5 (Dec. 1976), 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&ndash;574.

== 外部リンク ==
* [http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Prim.shtml 最小木問題: プリムのアルゴリズム]
* [http://www.cut-the-knot.org/Curriculum/Games/Mazes.shtml クラスカル法とプリム法で迷路を生成して解く] at cut-the-knot
* [http://students.ceid.upatras.gr/~papagel/project/prim.htm プリム法のアニメーション]
* [http://www.mincel.com/java/prim.html Prim's Algorithm] Java アプレット

{{アルゴリズム}}

{{DEFAULTSORT:ふりむのあるこりすむ}}
[[Category:グラフ理論]]
[[Category:アルゴリズム]]
[[Category:数学に関する記事]]
[[Category:組合せ最適化]]
[[Category:数学のエポニム]]
[[Category:エドガー・ダイクストラ]]