187 プリムのアルゴリズム

187 プリムのアルゴリズム

プリムのアルゴリズムは、グラフ理論における最小全域木を求めるための代表的な手法で、特に重み付き無向グラフに適用されます。最小全域木とは、すべての頂点を結びつつ、閉路がなく、かつ全体の辺の重みの合計が最小となるような構造です。プリム法の特徴は、貪欲法に基づいていて、その時点で最も良い選択肢を一つずつ積み重ねていくという点にあります。

このアルゴリズムでは、まずグラフ中の任意の1つの頂点から処理を開始します。その頂点に直接つながる辺の中で、最も重みの小さいものを選び、つながった先の頂点を新たに「木」の一部として追加します。その後も常に、「すでに木に含まれている頂点」と「まだ含まれていない頂点」を結ぶ辺の中から、最も重みの小さいものを選んで追加していきます。この操作をすべての頂点が含まれるまで繰り返すことで、結果として最小全域木が得られます。

プリム法は、電線の敷設、通信ネットワークの設計、道路や鉄道の配線など、コストを最小にしながら全体をつなぐ必要があるさまざまな場面で利用されています。類似の方法としてクラスカル法もありますが、プリム法は頂点を中心に木を広げていくのに対し、クラスカル法は辺の重み順で選んでいくため、性質が異なります。特にプリム法は、辺が多い密なグラフにおいて高い性能を発揮する傾向があります。