プリム法（最小全域木MSTアルゴリズム）の仕組みとC++実装をわかりやすく解説

プリム法（最小全域木）とは

連結グラフ G(V,E) のすべての辺に重み（コスト）が与えられているとき、プリム法（Prim's Algorithm）はそのグラフから最小全域木（Minimum Spanning Tree: MST）を見つけ出すアルゴリズムです。

プリム法は「木を成長させる（growing tree）」アプローチを採用しています。まず開始地点となる種（シード）の頂点を1つ決め、その頂点を起点として木全体を育てていきます。

この問題は2つの集合を使って解きます。一方の集合には「すでに選択されたノード」を保持し、もう一方には「まだ考慮していないノード」を保持します。種となる頂点から隣接する頂点を、最小コストの辺に基づいて取り込むことで、ノードを1つずつ追加しながら木を成長させていきます。

• このアルゴリズムの計算量は O(V²) です。ここで V は頂点の数を表します。

なお、プリム法は貪欲法（グリーディ法）の一種であり、ダイクストラ法とよく似た考え方に基づいています。優先度付きキュー（ヒープ）を併用することで、計算量を O(E log V) まで改善できることでも知られています。

入力 − 隣接行列

出力

(0)---(1|1) (0)---(2|3) (0)---(3|4)
(1)---(0|1) (1)---(4|2)
(2)---(0|3)
(3)---(0|4)
(4)---(1|2) (4)---(5|2)
(5)---(4|2) (5)---(6|3)
(6)---(5|3)

アルゴリズム

prims(g: Graph, t: tree, start)

入力 − グラフ g、空の木 t、種となる頂点「start」
出力 − 辺を追加した後の木

Begin
    usedVert と unusedVert の2つの集合を定義する
    usedVert[0] := start、unusedVert[0] := φ
    start 以外のすべての頂点 i について
        usedVert[i] := φ
        unusedVert[i] := i   //未使用リストにすべての頂点を追加
    done
    while usedVert 内の頂点数 ≠ V do   //V は全ノード数
        min := ∞
        usedVert 配列のすべての頂点について
            グラフのすべての頂点について
                if min > cost[i,j] AND i ≠ j then
                    min := cost[i,j]
                    ed := i と j を結ぶ辺（ed のコスト := min）
            done
        done
        unusedVert[ed の終点] := φ
        辺 ed を木 t に追加する
        ed の始点を usedVert に追加する
    done
End

C++による実装例

#include<iostream>
#define V 7
#define INF 999
using namespace std;
//グラフのコスト行列
int costMat[V][V] = {
    {0, 1, 3, 4, INF, 5, INF},
    {1, 0, INF, 7, 2, INF, INF},
    {3, INF, 0, INF, 8, INF, INF},
    {4, 7, INF, 0, INF, INF, INF},
    {INF, 2, 8, INF, 0, 2, 4},
    {5, INF, INF, INF, 2, 0, 3},
    {INF, INF, INF, INF, 4, 3, 0}
};
typedef struct{
    int u, v, cost;
}edge;
class Tree{
    int n;
    edge edges[V-1]; //木の辺の数は（頂点数 − 1）
    public:
    Tree(){
        n = 0;
    }
    void addEdge(edge e){
        edges[n] = e; //辺 e を木に追加
        n++;
    }
    void printEdges(){ //辺・コスト・合計コストを表示
        int tCost = 0;
        for(int i = 0; i<n; i++){
            cout << "Edge: " << char(edges[i].u+'A') << "--" << char(edges[i].v+'A');
            cout << " And Cost: " << edges[i].cost << endl;
            tCost += edges[i].cost;
        }
        cout << "Total Cost: " << tCost << endl;
    }
    friend void prims(Tree &tre, int start);
};
void prims(Tree &tr, int start){
    int usedVert[V], unusedVert[V];
    int i, j, min, p;
    edge ed;
    //初期化
    usedVert[0] = start; p = 1;
    unusedVert[0] = -1;//-1 はその場所が空であることを示す
    for(i = 1; i<V; i++){
        usedVert[i] = -1;//最初の要素以外はすべて空
        unusedVert[i] = i;//頂点で埋める
    }
    tr.n = 0;
    //辺を求めて木に追加
    while(p != V){ //p は usedVert 配列内の頂点数
        min = INF;
        for(i = 0; i<p; i++){
            for(j = 0; j<V; j++){
                if(unusedVert[j] != -1){
                    if(min > costMat[i][j] && costMat[i][j] != 0){
                        //u が考慮済みで v がまだ未考慮の
                        //最小コストの辺を探す
                        min = costMat[i][j];
                        ed.u = i; ed.v = j; ed.cost = min;
                    }
                }
            }
        }
        unusedVert[ed.v] = -1;//v を未使用頂点から削除
        tr.addEdge(ed);
        usedVert[p] = ed.u; p++;//u を使用済み頂点に追加
    }
}
int main(){
    Tree tr;
    prims(tr, 0); //開始ノードは 0
    tr.printEdges();
}

出力結果

(0)---(1|1) (0)---(2|3) (0)---(3|4)
(1)---(0|1) (1)---(4|2)
(2)---(0|3)
(3)---(0|4)
(4)---(1|2) (4)---(5|2)
(5)---(4|2) (5)---(6|3)
(6)---(5|3)