|
プリム法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。全域木（対象となるグラフの全頂点を含む辺の部分集合で構成される木）のうち、その辺群の重みの総和が最小となる木を求めるものである。このアルゴリズムは1930年に数学者 Vojtěch Jarník が発見し、1957年に計算機科学者ロバート・C・プリムが独自に発見、さらに1959年にはエドガー・ダイクストラが再発見しダイクストラ法の論文に記載している。そのため、DJP法、Jarník法、Prim-Jarník法などとも呼ばれることがある。アルゴリズムの発想や計算量は同時期に発表されたダイクストラ法に類似している。 == アルゴリズムの解説 == このアルゴリズムでは1つの辺から始めて、全頂点を覆うようになるまで連続的に木の大きさを拡大していく。 * 入力: 重み付きグラフ（頂点集合 V、辺集合 E） * 出力: Vnew と Enew が最小全域木を表している。 Vnew = 、ここで x は V の元であり、任意のノード（出発点） Enew = while (Vnew ≠ V) Vnew に含まれる頂点 u と 含まれない頂点 v を結ぶ重みが最小の辺 (u, v) を E から選択（同じ重みの辺が複数あるときは、どちらを選んでも良い） v を Vnew に加える (u, v) を Enew に加える 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「プリム法」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Prim's algorithm 」があります。 スポンサード リンク
|