プリム法とクラスカル法の違いを徹底解説!最小全域木(MST)アルゴリズムの比較

はじめに

本記事では、グラフ理論における代表的なアルゴリズムであるプリム法(Prim's Algorithm)とクラスカル法(Kruskal's Algorithm)の違いについて詳しく解説します。どちらも最小全域木(Minimum Spanning Tree:MST)を求めるための貪欲法(グリーディアルゴリズム)ですが、アプローチや特性が大きく異なります。

前提知識：最小全域木(MST)とは

• 連結かつ無向のグラフが与えられたとき、全域木(スパニングツリー)とは、そのグラフのすべての頂点を接続する木構造の部分グラフを指します。
• 1つのグラフから複数の全域木が作られる可能性があります。
• 最小全域木(MST)とは、重み付き連結無向グラフにおいて、他のどの全域木よりも重みが小さい(または等しい)全域木のことです。
• 全域木の重みは、その木に含まれるすべての辺の重みを合計したものとして定義されます。

クラスカル法(Kruskal's Algorithm)とは

クラスカル法は、辺を基準に最小全域木を構築していく貪欲法アルゴリズムです。

主な特徴

• 最小の重みを持つ辺から木を構築していきます。
• 各ノードは一度だけ走査されます。
• 疎なグラフ(辺の数が少ないグラフ)で高速に動作します。
• 時間計算量は O(E log V)(V:頂点数、E:辺数)です。
• 非連結のグラフ(分断された成分を含むグラフ)にも適用できます。

クラスカル法によるMSTの求め方

1. すべての辺を重みの昇順にソートします。
2. 最も重みの小さい辺を選択します。
3. その辺が、それまでに構築した全域木とともにサイクル(閉路)を形成しないか確認します。
4. サイクルが形成されない場合は、その辺を採用します。
5. サイクルが形成される場合は、その辺を破棄します。
6. 全域木の辺の数が V−1 個になるまで、手順2〜5を繰り返します。

プリム法(Prim's Algorithm)とは

プリム法は、頂点を基準に最小全域木を一つずつ成長させていく貪欲法アルゴリズムです。クラスカル法と同様に貪欲法に分類されます。

主な特徴

• 空の全域木から開始し、2つの頂点集合を管理します。
• 片方の集合にはすでにMSTに含まれた頂点を、もう片方には未追加の頂点を格納します。
• 各ステップで、2つの集合を結ぶすべての辺を検討し、その中で最も重みの小さい辺を選択します。
• 選ばれた辺のもう一方の端点を、MST側の集合へ移動させます。
• MSTはグラフ内の任意の頂点から構築を開始できます。
• 最小距離の値を更新するため、同じノードを複数回訪問する場合があります。
• 時間計算量は O(V²)(V:頂点数)です。フィボナッチヒープを使用することで O(E + V log V) まで改善できます。
• 密なグラフ(辺の数が多いグラフ)で高速に動作します。
• 連結グラフのみに対応しており、非連結グラフでは使用できません。

プリム法によるMSTの求め方

1. MSTにすでに含まれている頂点を記録するための集合 mstSet を作成します。
2. 入力グラフのすべての頂点にキー値(key value)を割り当てます。
3. 初期状態では、すべてのキー値を「∞(INFINITE)」に設定します。
4. 最初に選ばれるよう、開始頂点のキー値のみ「0」を設定します。
5. mstSet がすべての頂点を含むまで、以下の手順を繰り返します。
   • mstSet に含まれず、かつキー値が最小である頂点 u を選択します。
   • 頂点 u を mstSet に追加します。
   • u のすべての隣接頂点を反復処理し、キー値を更新します。
   • 隣接頂点 v ごとに、辺 u–v の重みが v の現在のキー値より小さい場合は、v のキー値をその重みに更新します。

プリム法とクラスカル法の比較まとめ

まとめ

クラスカル法は「辺」に着目して全体をソートしながら構築するのに対し、プリム法は「頂点」に着目して木を一つずつ成長させます。疎なグラフならクラスカル法、密なグラフならプリム法が適しています。グラフの性質や要件に応じて、両者を上手く使い分けることが重要です。