C++で学ぶプリム法：隣接行列による最小全域木のシンプルな実装

プリム法（Prim's Algorithm）は、与えられた重み付き無向グラフから最小全域木（Minimum Spanning Tree）を求めるための貪欲法（グリーディ法）ベースのアルゴリズムです。

基本用語のおさらい

重み付きグラフ（Weighted Graph）とは、すべての辺に重み（コストや距離などの数値）が割り当てられているグラフのことです。

無向グラフ（Undirected Graph）とは、すべての辺が双方向につながっているタイプのグラフです。ある頂点から別の頂点へ移動できる場合、その逆方向にも必ず移動できます。

最小全域木（Minimum Spanning Tree）とは、元のグラフのすべての頂点を含みながら閉路（サイクル）を持たず、かつ含まれる辺の重みの合計が最小となる部分グラフのことです。

この記事では、プリム法を使って最小全域木を求める方法を解説します。一般的にこのアルゴリズムは2つの配列を使用しますが、本稿の実装では1つの配列だけで処理を行うシンプルなアプローチを採用しています。

アルゴリズムの基本的な流れ

1. 任意の頂点を1つ選び、MST（最小全域木）の候補集合に追加します。
2. MSTに含まれる頂点と含まれない頂点をつなぐ辺の中から、重みが最小のものを選択します。
3. 選んだ辺と、その先の頂点をMSTに追加します。
4. 辺の本数が「頂点数 − 1」になるまで、手順2〜3を繰り返します。

この手法の計算量は O(V²) であり、密なグラフ（隣接行列で表現するのに適したグラフ）に対して効率的に動作します。

C++による実装例

以下は、隣接行列で表現されたグラフに対してプリム法を実装したC++プログラムです。

#include <bits/stdc++.h>
using namespace std;
#define V 5
bool createsMST(int u, int v, vector<bool> inMST){
    if (u == v)
        return false;
    if (inMST[u] == false && inMST[v] == false)
        return false;
    else if (inMST[u] == true && inMST[v] == true)
        return false;
    return true;
}
void printMinSpanningTree(int cost[][V]){
    vector<bool> inMST(V, false);
    inMST[0] = true;
    int edgeNo = 0, MSTcost = 0;
    while (edgeNo < V - 1) {
        int min = INT_MAX, a = -1, b = -1;
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (cost[i][j] < min) {
                    if (createsMST(i, j, inMST)) {
                        min = cost[i][j];
                        a = i;
                        b = j;
                    }
                }
            }
        }
        if (a != -1 && b != -1) {
            cout<<"Edge "<<edgeNo++<<" : ("<<a<<" , "<<b<<" ) : cost = "<<min<<endl;
            MSTcost += min;
            inMST[b] = inMST[a] = true;
        }
    }
    cout<<"Cost of Minimum spanning tree ="<<MSTcost;
}
int main() {
    int cost[][V] = {
        { INT_MAX, 12, INT_MAX, 25, INT_MAX },
        { 12, INT_MAX, 11, 8, 12 },
        { INT_MAX, 11, INT_MAX, INT_MAX, 17 },
        { 25, 8, INT_MAX, INT_MAX, 15 },
        { INT_MAX, 12, 17, 15, INT_MAX },
    };
    cout<<"The Minimum spanning tree for the given tree is :\n";
    printMinSpanningTree(cost);
    return 0;
}

出力結果

The Minimum spanning tree for the given tree is :
Edge 0 : (0 , 1 ) : cost = 12
Edge 1 : (1 , 3 ) : cost = 8
Edge 2 : (1 , 2 ) : cost = 11
Edge 3 : (1 , 4 ) : cost = 12
Cost of Minimum spanning tree =43

このプログラムでは、関数 createsMST() が「選ぼうとしている辺がMSTの構築条件（一方の端点のみがMSTに含まれること）を満たすか」を判定し、printMinSpanningTree() が最小の重みを持つ辺を繰り返し探索してMSTを構築しています。最終的に、5つの頂点を持つこのグラフの最小全域木のコストは 43 となることが確認できます。