クラスカル法による最小全域木（MST）アルゴリズム ― C++での貪欲法の実装

最小全域木（MST）とは？

全域木（spanning tree）とは、連結かつ無向のグラフにおいて、すべての頂点を接続する部分グラフのことです。ひとつのグラフには複数の全域木が存在しえますが、その中で辺の重みの合計が他のどの全域木よりも等しいか小さくなるものを最小全域木（Minimum Spanning Tree：MST）と呼びます。各辺には重みが割り当てられており、それらの総和がその全域木の重みとなります。頂点数を V とすると、最小全域木に含まれる辺の数は必ず (V − 1) 本になります。

クラスカル法で最小全域木を求める手順

1. すべての辺を、重みの昇順（非降順）に並べ替えます。

2. 重みが最も小さい辺から順に取り出し、その辺を採用しても閉路（サイクル）が形成されない場合にのみ結果へ追加します。

3. 採用済みの辺の数が (V − 1) 本に達するまで、手順2を繰り返します。

ここで用いられるのが貪欲法（グリーディ法）です。「その時点で重みが最小となる辺を選ぶ」という判断を繰り返すことで、全体として最適な解に到達します。

例として挙げるグラフでは頂点数が 9 であるため、最小全域木に含まれる辺は (9 − 1) ＝ 8 本となります。

辺を重み順にソートした結果

重み    始点    終点
21      27      26
22      28      22
22      26      25
24      20      21
24      22      25
26      28      26
27      22      23
27      27      28
28      20      27
28      21      22
29      23      24
30      25      24
31      21      27
34      23      25

次に、ソートされた順序に従って各辺を順番に判定していきます。

辺 26–27 → 閉路が形成されないため採用

辺 28–22 → 閉路が形成されないため採用

辺 26–25 → 閉路が形成されないため採用

辺 20–21 → 閉路が形成されないため採用

辺 22–25 → 閉路が形成されないため採用

辺 28–26 → 閉路が形成されるため破棄

辺 22–23 → 閉路が形成されないため採用

辺 27–28 → 閉路が形成されるため破棄

辺 20–27 → 閉路が形成されないため採用

辺 21–22 → 閉路が形成されるため破棄

辺 23–24 → 閉路が形成されないため採用

これで採用された辺の数が (V − 1) 本に達したため、アルゴリズムはここで終了です。

C++での実装例

以下は、Union-Find（素集合データ構造）を使って閉路の有無を効率的に判定する実装例です。find() 関数で頂点が属する木の根を求め、Union() 関数でランク（木の深さ）を考慮しながら2つの集合を統合することで、閉路の形成を高速に検出できます。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Edge {
    int src, dest, weight;
};
struct Graph {
    int V, E;
    struct Edge* edge;
};
struct Graph* createGraph(int V, int E){
    struct Graph* graph = (struct Graph*)(malloc(sizeof(struct Graph)));
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*)malloc(sizeof( struct Edge)*E);
    return graph;
}
struct subset {
    int parent;
    int rank;
};
int find(struct subset subsets[], int i){
    if (subsets[i].parent != i)
        subsets[i].parent
= find(subsets, subsets[i].parent);
    return subsets[i].parent;
}
void Union(struct subset subsets[], int x, int y){
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else{
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}
int myComp(const void* a, const void* b){
    struct Edge* a1 = (struct Edge*)a;
    struct Edge* b1 = (struct Edge*)b;
    return a1->weight > b1->weight;
}
void KruskalMST(struct Graph* graph){
    int V = graph->V;
    struct Edge
    result[V];
    int e = 0;
    int i = 0;
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
    struct subset* subsets
    = (struct subset*)malloc(V * sizeof(struct subset));
    for (int v = 0; v < V; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
    while (e < V - 1 && i < graph->E) {
        struct Edge next_edge = graph->edge[i++];
        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);
        if (x != y) {
            result[e++] = next_edge;
            Union(subsets, x, y);
        }
    }
    printf("Following are the edges in the constructed MST\n");
    int minimumCost = 0;
    for (i = 0; i < e; ++i){
        printf("%d -- %d == %d\n", result[i].src,
        result[i].dest, result[i].weight);
        minimumCost += result[i].weight;
    }
    printf("Minimum Cost Spanning tree : %d",minimumCost);
    return;
}
int main(){
    /* Let us create the following weighted graph
    30
    0--------1
    | \        |
    26|  25\ |15
    | \ |
    22--------23
    24 */
    int V = 24;
    int E = 25;
    struct Graph* graph = createGraph(V, E);
    graph->edge[0].src = 20;
    graph->edge[0].dest = 21;
    graph->edge[0].weight = 30;
    graph->edge[1].src = 20;
    graph->edge[1].dest = 22;
    graph->edge[1].weight = 26;
    graph->edge[2].src = 20;
    graph->edge[2].dest = 23;
    graph->edge[2].weight = 25;
    graph->edge[3].src = 21;
    graph->edge[3].dest = 23;
    graph->edge[3].weight = 35;
    graph->edge[4].src = 22;
    graph->edge[4].dest = 23;
    graph->edge[4].weight = 24;
    KruskalMST(graph);
    return 0;
}

実行結果

Following are the edges in the constructed MST
22 -- 23 == 24
20 -- 23 == 25
20 -- 21 == 30
Minimum Cost Spanning tree : 79

出力を見ると、重み 24・25・30 の3本の辺が採用され、構築された最小全域木の総コストは 79 となっていることがわかります。

まとめ

本記事では、クラスカルの最小全域木アルゴリズムについて、貪欲法の考え方とともにC/C++のコード例を通して解説しました。辺を重み順に並べ替え、閉路を作らない辺だけを選んでいくというシンプルな手順で、与えられたグラフから最小コストの全域木を効率的に求められます。同じロジックはJavaやPythonなど、他のプログラミング言語でも容易に実装でき、ネットワーク設計などさまざまな分野で応用されています。本記事が皆さんの学習のお役に立てば幸いです。