プリム法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。全域木（対象となるグラフの全頂点を含む辺の部分集合で構成される木）のうち、その辺群の重みの総和が最小となる木を求めるものである。このアルゴリズムは1930年に数学者 Vojtěch Jarník が発見し、1957年に計算機科学者ロバート・C・プリムが独自に発見、さらに1959年にはエドガー・ダイクストラが再発見しダイクストラ法の論文に記載している。そのため、DJP法、Jarník法、Prim-Jarník法などとも呼ばれることがある。アルゴリズムの発想や計算量は同時期に発表されたダイクストラ法に類似している。このアルゴリズムでは1つの辺から始めて、全頂点を覆うようになるまで連続的に木の大きさを拡大していく。 V = {x}、ここで x は V の元であり、任意のノード（出発点）V は頂点の数、E は辺の数。「重みが最小の辺」をどのように探索するかで計算量が変わる。グラフを隣接行列で表した単純な実装で、重みの配列を探索して重みが最小の辺を求める場合、formula_1 の時間がかかる。単純な二分ヒープと隣接リストを使うと、formula_2 の時間がかかる。より洗練されたフィボナッチヒープを使うと、E が formula_3 の程度まで稠密であれば、時間は formula_4 とかなり改善される。"P" を重み付き連結グラフとする。プリム法の繰り返しでは、毎回ある部分グラフからその外部へと接続している辺を探し出す。"P" は連結グラフなので、全ての頂点に常に道が存在する。プリム法の出力 "Y" に追加される辺と頂点はつねに接合しているため、"Y" は木である。"Y" が P の最小全域木であるとする。"Y"="Y" なら、"Y" は最小全域木である。そうでない場合、"Y" にあって "Y" にない辺のうち、"Y" の構築時に最初に追加された辺を "e" とし、"e" が追加される以前に追加された辺に接合している頂点の集合を "V" とする。"e" の端点の一方は "V" にあり、もう一方はそうではない。"Y" は "P" の全域木なので、"Y" にはその2つの端点をつなぐ道がある。その道をたどると、"V" 内の頂点から "V" 外の頂点への辺 "f" に必ず遭遇する。さて、"Y" に "e" を追加した時の繰り返しにおいて、"e" よりも "f" の方が重みが小さければ "f" が追加されていただろう。しかし "f" は追加されなかったので、次の結論が得られる。"Y" から "f" を除いて "e" を追加したグラフを "Y" とする。"Y" が連結グラフであり、"Y" と同数の辺を持ち、辺の重みの総和が "Y" より小さいことは容易に示すことができる。従って、これも "P" の最小全域木であり、"e" を含み、それ以前に "V" の構築の際に追加された全ての辺を含んでいる。以上を繰り返し適用していくと、"Y" と全く同じ "P" の最小全域木を得られる。以上から、"Y" は最小全域木であることがわかる。最小全域木問題の他のアルゴリズムとしてクラスカル法やがある。

出典:wikipedia