プリム法による最小全域木アルゴリズムの徹底解説

はじめに

重み付き連結グラフ G(V, E) のすべての辺にコストが与えられているとき、プリム法はこのグラフから最小全域木を見つけ出すアルゴリズムです。

木を成長させるアプローチ

プリム法は、木を少しずつ成長させていく手法を採用しています。まず始点となる頂点を選び、そこから隣接する頂点の中で最もコストの低い辺を順番に選びながら、木を一つずつ拡張していきます。

具体的には、次の図のようなグラフを例として考えます。

基本的な考え方：2つの集合による管理

この問題は、2つの集合を使って効率的に解くことができます。

• 選択済み集合：すでに木に含まれた頂点を管理します。
• 未考慮集合：まだ木に追加されていない頂点を管理します。

始点からスタートし、未考慮の頂点との間で最もコストの小さい辺を探して、その頂点を1つずつ木へと追加していきます。これにより、最終的に全ての頂点を含む最小全域木が完成します。

計算量

この実装における時間計算量は O(V²) です。ここで 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
    define two sets as usedVert, unusedVert
    usedVert[0] := start and unusedVert[0] := φ

    for all vertices except start do
        usedVert[i] := φ;
        unusedVert[i] := i    //add all vertices in unused list
    done

    while number of vertices in usedVert ≠ V do    //V is number of total nodes
        min := ∞;
        for all vertices of usedVert array do
            for all vertices of the graph do
                if min > cost[i,j] AND i ≠ j then
                    min := cost[i,j]
                    ed := edge between i and j, and cost of ed := min
            done
        done

        unusedVert[destination of ed] := φ;
        add edge ed into the tree t
        add source of ed into usedVert
    done
End

C++での実装例

以下は、C++でプリム法を実装したサンプルコードです。

#include<iostream>
#define V 7
#define INF 999
using namespace std;

//Cost matrix of the graph
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];     //as a tree has vertex-1 edges
    public:
        Tree() {
            n = 0;
        }

        void addEdge(edge e) {
            edges[n] = e;     //add edge e into the tree
            n++;
        }

        void printEdges() {     //print edge, cost and total cost
            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;

    //initialize
    usedVert[0] = start; p = 1;
    unusedVert[0] = -1;     //-1 indicates the place is empty

    for(i = 1; i<V; i++) {
        usedVert[i] = -1;     //all places except first is empty
        unusedVert[i] = i;   //fill with vertices
    }

    tr.n = 0;
    //get edges and add to tree
    while(p != V) {      //p is number of vertices in usedVert array
        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) {
                        //find the edge with minimum cost
                        //such that u is considered and v is not considered yet
                        min = costMat[i][j];
                        ed.u = i; ed.v = j; ed.cost = min;
                    }
                }
            }
        }
        unusedVert[ed.v] = -1;      //delete v from unusedVertex
        tr.addEdge(ed);
        usedVert[p] = ed.u; p++;    //add u to usedVertex
    }
}

main() {
    Tree tr;
    prims(tr, 0);      //starting node 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)

このように、プリム法は貪欲法の一種であり、常に現時点で最もコストの低い辺を選択することで、全体として最小のコストを持つ全域木を構築できます。