Prim 法

2025年10月20日

Prim 法

英語表記: Prim’s Algorithm

概要

Prim 法（プリム法）は、重み付き無向グラフにおいて、すべての頂点を結びつけながら、使用する辺（エッジ）の重みの総和が最小となる木構造、すなわち最小全域木（MST: Minimum Spanning Tree）を構築するための効率的なグラフアルゴリズムです。この手法は、ネットワーク設計やインフラ整備など、最小コストで全体を接続したいという要求に応えるために、アルゴリズムと計算量の分野で非常に重要な位置を占めています。特定の開始点から木を成長させていく「頂点ベース」の貪欲法を採用しているのが特徴です。

詳細解説

Prim法は、最小全域木という特定の課題を解決するために設計された、洗練されたアプローチです。このアルゴリズムは、グラフアルゴリズムの中でも特にネットワーク最適化問題に適用されます。

目的と基本原理

Prim法の目的は、与えられたグラフ $G=(V, E)$（$V$は頂点の集合、$E$は辺の集合）から、すべての頂点 $V$ を含み、辺の重みの合計が最小となる部分グラフ $T$（木構造）を見つけ出すことです。

このアルゴリズムの根幹にあるのは貪欲法（Greedy Algorithm）の考え方です。貪欲法とは、各段階で局所的に最も最適と思われる選択肢を選び続けることで、最終的に全体として最適解に到達しようとする戦略です。Prim法の場合、これは「既に最小全域木の一部として選ばれた頂点の集合」と「まだ選ばれていない頂点」を結ぶ辺の中で、最も重みが小さい辺を常に選択し続けることに相当します。

Prim法の具体的な動作ステップ

Prim法は、成長する木をイメージすると理解しやすいです。

初期化: グラフ内の任意の頂点 $v_0$ を選び、これを最小全域木（$T$）の初期集合に含めます。
辺の選択: 現在 $T$ に含まれている頂点と、まだ $T$ に含まれていない頂点を結ぶすべての辺（これを「境界辺」と呼びます）をリストアップします。
貪欲な選択: リストアップされた境界辺の中から、重みが最小である辺 $e_{min}$ を選びます。
木の成長: 選ばれた辺 $e_{min}$ と、その辺が結ぶ新しい頂点 $v_{new}$ を $T$ に追加します。
終了判定: すべての頂点が $T$ に含まれるまで（すなわち、$|T| = |V|$ となるまで）、ステップ2～4を繰り返します。

このステップを繰り返すたびに、木は一歩ずつ拡張していきます。選ばれた辺 $e_{min}$ は、常にその時点でのネットワーク拡張における「最も安価な接続」を意味するため、最終的な総コストの最小性が保証されるという仕組みです。これは非常に賢いやり方だと感心しますね。

アルゴリズムと計算量

Prim法をアルゴリズムと計算量の観点から見ると、その効率性は非常に重要です。

単純な実装: 頂点 $V$ の数が $N$ の場合、各ステップで最適な辺を探すためにすべての辺をチェックすると、計算量は $O(N^2)$ となります。
効率的な実装: 優先度付きキュー（ヒープ構造）を用いて、次に選ぶべき最小重みの辺を効率的に管理することで、計算量は $O(E + V \log V)$ （$E$ は辺の数、$V$ は頂点の数）に改善されます。

グラフが非常に大規模になる現代のIT環境では、この計算量の違いが実用上の速度に直結します。疎なグラフ（辺が少ないグラフ）に対しては $O(E + V \log V)$ の実装が極めて高速であり、Prim法が最小全域木アルゴリズムとして広く採用される理由の一つとなっています。

具体例・活用シーン

Prim法は、理論的な美しさだけでなく、現実のさまざまな最適化問題に応用されています。

アナロジー：光ファイバー網の最適設計物語

想像してみてください。あなたは巨大な都市ネットワークの設計者です。都市内の主要なビルやデータセンター（頂点）すべてを、光ファイバーケーブル（辺）で接続する必要があります。ただし、ケーブルの敷設コスト（重み）は、地形や距離によって場所ごとに大きく変動します。あなたのミッションは、すべての拠点を繋ぎながら、総敷設コストを最小にすることです。

ここでPrim法が登場します。

まず、中心となるデータセンター（始点）を一つ選びます。
データセンターからまだケーブルが届いていないビル群へ伸びる候補の接続ルートをすべてリストアップします。
そのリストの中から、最も敷設コストが安いルートを選んで実際にケーブルを敷設します。
この新しいビルがネットワークに加わったことで、接続済みの拠点グループ（MST集合）が拡大します。
次に、この拡大したグループ全体から見て、外側の未接続のビルへ伸びる最も安いルートを再び選びます。

この作業を繰り返すことで、常に「現在の接続状況」を基準に「次に最もお得な拡張」を選び続けることができます。結果として、ネットワーク全体が完成したとき、あなたは最小の予算で最高の接続性を持つ光ファイバー網を構築していることになります。これは、局所的な最適解の積み重ねが全体的な最適解を生み出す、Prim法の貪欲な戦略の力を示しています。

活用シーンの例

通信インフラ: 都市間の通信回線や、データセンター内のバックボーンネットワーク構築におけるコスト最小化。
物流・交通: 複数の倉庫や配送拠点間を最小距離で結ぶルート設計。
地質調査: 複数の調査地点を、最小限のパイプラインや観測網で接続する配置計画。

これらの応用例を通じて、Prim法が単なる学術的なアルゴリズムではなく、実社会における重要なアルゴリズムと計算量の応用例であることが分かります。

資格試験向けチェックポイント

ITパスポート、基本情報技術者、応用情報技術者などの資格試験において、Prim法はグラフアルゴリズムの知識を問う上で頻出するテーマです。特に最小全域木の文脈で確実に得点できるように準備しておきましょう。

Prim法とKruskal法の区別: 最小全域木を求める主要なアルゴリズムとして、Prim法（頂点ベース）とKruskal法（辺ベース）の違いを明確に理解することが必須です。Prim法は「成長する木に隣接する最小辺を選ぶ」、Kruskal法は「全辺をソートし、閉路を作らないように最小辺を選ぶ」と覚えましょう。この違いは頻繁に問われます。
動作のシミュレーション（トレース）: 複雑なグラフ図が与えられ、特定の開始点からPrim法を適用した際に、どの辺がどの順番で選択されるかを問う問題が出ます。必ず手順1から4を正確に適用し、特に「既に選ばれた頂点集合」と「未選択の頂点」の間の辺のみを考慮することを忘れないでください。
貪欲法の理解: Prim法がなぜ最小全域木を保証できるのか、その背景にある「貪欲法」の原理（局所的な最適解が全体的な最適解につながる）を理解しているかが問われることがあります。
計算量の比較: グラフの密度（疎/密）によって、Prim法とKruskal法のどちらが効率的かという比較問題が出題されることもあります。これはアルゴリズムと計算量カテゴリの典型的な出題パターンです。