クラスカル法による最小全域木アルゴリズムの解説とC++実装例

連結グラフ G(V, E) と、すべての辺の重み（コスト）が与えられたとき、クラスカルのアルゴリズム（Kruskal's algorithm）は、このグラフと各辺のコストをもとに最小全域木（Minimum Spanning Tree）を求めます。

クラスカル法は「マージツリーアプローチ」とも呼ばれる手法です。初期状態では各頂点がそれぞれ独立した木として存在しており、コストが最小の辺から順に選んで木同士を統合していくことで、最終的に1本の木を形成します。

具体的な手順としては、まず問題のすべての辺を列挙し、コストの昇順にソートします。続いて、リストからコストの小さい辺を順に取り出して木へ追加していきます。このとき毎回、その辺を追加すると閉路（サイクル）が形成されないかを判定します。閉路を形成する場合はその辺を破棄し、次の辺へ進みます。

閉路の判定には、各頂点がどの集合（木）に属しているかを管理する仕組みが使われます。2つの頂点がすでに同じ集合に属している場合、その間に辺を張ると必ず閉路になるためです。

このアルゴリズムの時間計算量は O(E log E)、または O(E log V) となります。ここで E は辺の数、V は頂点の数を表します。

入力と出力

入力:
隣接行列

出力:
Edge: B--A And Cost: 1
Edge: E--B And Cost: 2
Edge: F--E And Cost: 2
Edge: C--A And Cost: 3
Edge: G--F And Cost: 3
Edge: D--A And Cost: 4
Total Cost: 15

アルゴリズム

kruskal(g: Graph, t: Tree)

入力 − 与えられたグラフ g と空の木 t

出力 − 選択された辺を含む木 t

Begin
    グラフ g の各頂点について集合を作成する
    各頂点 u の集合に対して
        vertexSet[u] に u を追加する
    done

    辺リストをソートする
    count := 0
    while count <= V - 1 do       // 木は必ず V - 1 本の辺を持つ
        ed := edgeList[count]     // 辺リストから1本の辺を取り出す
        if ed の始点と終点が異なる集合に属する場合 then
            vertexSet[start] と vertexSet[end] をマージする
            ed を木 t に追加する
        count := count + 1
    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;

void swapping(edge &e1, edge &e2) {
    edge temp;
    temp = e1;
    e1 = e2;
    e2 = temp;
}

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;
        }
};

class VSet {
    int n;
    int set[V];   // 最大 V 個の頂点を保持できる集合
    public:
        VSet() {
            n = -1;
        }

        void addVertex(int vert) {
            set[++n] = vert;   // 頂点を集合に追加
        }

        int deleteVertex() {
            return set[n--];
        }

        friend int findVertex(VSet *vertSetArr, int vert);
        friend void merge(VSet &set1, VSet &set2);
};

void merge(VSet &set1, VSet &set2) {
    // 2つの頂点集合をマージする
    while(set2.n >= 0)
        set1.addVertex(set2.deleteVertex());
}

int findVertex(VSet *vertSetArr, int vert) {
    // 各頂点集合の中から指定された頂点を検索する
    for(int i = 0; i<V; i++)
        for(int j = 0; j<=vertSetArr[i].n; j++)
            if(vert == vertSetArr[i].set[j])
                return i;   // i 番目の頂点集合で見つかった
}

int findEdge(edge *edgeList) {
    // コスト行列から辺を取り出し edgeList に格納する
    int count = -1, i, j;
    for(i = 0; i<V; i++)
        for(j = 0; j<i; j++)
            if(costMat[i][j] != INF) {
                count++;
                // count 番目の位置に辺情報を格納
                edgeList[count].u = i; edgeList[count].v = j;
                edgeList[count].cost = costMat[i][j];
            }
    return count+1;
}

void sortEdge(edge *edgeList, int n) {
    // 辺をコストの昇順にソートする
    int flag = 1, i, j;

    for(i = 0; i<(n-1) && flag; i++) {   // 改良版バブルソートを使用
        flag = 0;
        for(j = 0; j<(n-i-1); j++)
            if(edgeList[j].cost > edgeList[j+1].cost) {
                swapping(edgeList[j], edgeList[j+1]);
                flag = 1;
            }
    }
}

void kruskal(Tree &tr) {
    int ecount, maxEdge = V*(V-1)/2;   // グラフが持ちうる最大の辺数は n(n-1)/2
    edge edgeList[maxEdge], ed;
    int uloc, vloc;
    VSet VSetArray[V];
    ecount = findEdge(edgeList);

    for(int i = 0; i < V; i++)
        VSetArray[i].addVertex(i);   // 各集合は最初1要素のみ
    sortEdge(edgeList, ecount);      // ecount はグラフの辺数
    int count = 0;

    while(count <= V-1) {
        ed = edgeList[count];
        uloc = findVertex(VSetArray, ed.u);
        vloc = findVertex(VSetArray, ed.v);

        if(uloc != vloc) {   // 始点と終点が同じ集合かどうか判定
            merge(VSetArray[uloc], VSetArray[vloc]);
            tr.addEdge(ed);
        }
        count++;
    }
}

int main() {
    Tree tr;
    kruskal(tr);
    tr.printEdges();
}

出力結果

Edge: B--A And Cost: 1
Edge: E--B And Cost: 2
Edge: F--E And Cost: 2
Edge: C--A And Cost: 3
Edge: G--F And Cost: 3
Edge: D--A And Cost: 4
Total Cost: 15

このプログラムでは、頂点数が 7 なので最小全域木は V - 1 = 6 本の辺で構成されます。上記の出力から、選ばれた 6 本の辺の合計コストが 15 となる最小全域木が得られていることがわかります。