アルゴリズム

C言語によるクラスカル法の実装解説：貪欲アルゴリズムで最小全域木(MST)を生成する方法

2025-01-17更新日: 2025-01-17

本記事では、C言語でクラスカル法を用いて最小全域木(MST)を生成する実装手法を解説します。

クラスカル法は、グラフ内の辺を重み順に選び、サイクルができないよう管理しながら最小全域木を構築する貪欲アルゴリズムです。

実際のコード例を通して、各工程の実装ポイントを分かりやすく説明します。

目次から探す

クラスカル法の基本
C言語による実装の準備
- 必要なデータ構造
- 開発環境と使用ライブラリ
実装ステップの詳細
コード例と各処理の解説
- main関数の役割と構成
- 補助関数の連携と詳細
まとめ

クラスカル法の基本

最小全域木(MST)の定義と目的

最小全域木(Minimum Spanning Tree, MST)とは、グラフが持つすべての頂点を連結しつつ、辺の重みの合計が最小となる木構造のことです。

例えば、通信ネットワークの構築や交通網の設計などでは、コストを最小限にするためにMSTが利用されることが多く、グラフ内の不要な辺を排除して効率的な接続を実現する役割を果たします。

MSTは以下の条件を満たす必要があります：

グラフ内のすべての頂点が一つの連結成分に含まれる
辺の数は (頂点数 – 1) 本である
辺の重みの合計が最小である

貪欲アルゴリズムの仕組み

クラスカル法は「貪欲法」と呼ばれる戦略に基づいています。

貪欲法では、その時点で最もよい選択を繰り返すことで全体の最適解に近づける手法です。

クラスカル法では、まずすべての辺を重みの小さい順に並べ、その順に辺を取り出していきます。

具体的には以下の流れとなります：

隣接する頂点を接続する辺を重みの小さい順にソートする
ソートされた順に辺を採用し、採用した辺がサイクルを形成しなければMSTに追加する

このように、局所的な最適選択を連続していくことで、全体として最小の接続構造が得られる仕組みとなっています。

Union-Findによるサイクル検出

クラスカル法において、既存の部分木に新たな辺を追加する際、サイクルが発生しないかをチェックすることが重要です。

このとき利用されるのがUnion-Find(ディスジョイントセット)というデータ構造です。

Union-Findは以下の2つの基本操作により、効率的に集合の管理を行います：

find関数：指定した要素が属する集合の代表元(根)を返す
union関数：2つの集合を統合する

これにより、既に連結されている頂点群に対して新しい辺を追加した場合に、サイクルができるかどうかを高速に判定することができます。

C言語による実装の準備

必要なデータ構造

構造体による辺の表現

C言語でクラスカル法を実装する際、各辺を管理するために構造体を用いるのが一般的です。

例えば、以下のような構造体 Edge を定義することができます。

各メンバの意味は以下の通りです：

from：辺の始点となる頂点
to：辺の終点となる頂点
weight：辺の重み

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int from;
    int to;
    int weight;
} Edge;

配列とリンクリストの利用

クラスカル法の実装では、辺の管理に配列を使用するケースが多いです。

配列は固定長でメモリが連続しているため、ソート処理などで高速にアクセスできるメリットがあります。

一方、場合によっては動的なグラフ操作や部分木の管理にリンクリストを用いることも検討されることがあります。

ただし、基本的な実装では配列を用いることが多く、リンクリストは補助的な利用に留めるとよいでしょう。

開発環境と使用ライブラリ

C言語の環境でクラスカル法を実装する場合、標準ライブラリとして <stdio.h> や <stdlib.h> を利用します。

具体的には、以下のライブラリが必要です：

<stdio.h>：入出力操作用
<stdlib.h>：メモリ管理、ソート関数 qsort の利用のため
必要に応じて <limits.h> や <stdbool.h> も利用すると便利です

実装ステップの詳細

グラフの入力と初期化

頂点数と辺数の管理

グラフの入力では、最初に頂点数と辺数を受け取ることが一般的です。

例えば、ユーザインターフェースやファイル、コマンドライン引数などから得た頂点数と辺数を変数に格納し、後続のメモリ確保や処理に利用します。

変数名 numVertices や numEdges として管理すると分かりやすくなります。

メモリ確保と初期化処理

入力後は、辺情報を格納するための配列のために動的メモリ確保を行います。

以下は配列のメモリを malloc を用いて確保する例です：

#include <stdio.h>
#include <stdlib.h>
int main(void) {
    int numVertices, numEdges;
    // 例として、標準入力から頂点数と辺数を読み込みます
    scanf("%d %d", &numVertices, &numEdges);
    // エッジ情報を保存するための配列を確保する
    Edge* edges = (Edge*)malloc(numEdges * sizeof(Edge));
    if (edges == NULL) {
        printf("エッジ配列のメモリ確保に失敗しました\n");
        return 1;
    }
    // ここで入力により各辺の情報を取得する処理を追加
    free(edges);
    return 0;
}

(サンプル入力に応じた出力が表示されます)

辺のソート処理の実装

ソート関数の設計と実装

辺のソートはクラスカル法の重要な処理の一つです。

重みが小さい順に並べ替えるために、標準ライブラリの qsort を利用できます。

比較関数を自作して、辺の重みを基準にソートする仕組みを作ります。

以下は compareEdge関数のサンプルです：

#include <stdio.h>
#include <stdlib.h>
int compareEdge(const void* a, const void* b) {
    Edge* edgeA = (Edge*)a;
    Edge* edgeB = (Edge*)b;
    return edgeA->weight - edgeB->weight;
}

ソートアルゴリズムの選定

C言語では、簡単に利用可能な qsort関数を用いることで、比較的高速なソートが実現できます。

qsort は安定性が保証されないものの、クラスカル法においては安定性は必須ではないため、実装の簡便さが優先される場合に有用です。

Union-Findによるサイクル管理

find関数の実装

Union-Find構造における find関数は、指定した要素が属する集合の代表元を返す処理を行います。

以下はパス圧縮を実装したサンプルコードです：

#include <stdio.h>
#include <stdlib.h>
int find(int* parent, int vertex) {
    if (parent[vertex] != vertex) {
        parent[vertex] = find(parent, parent[vertex]);  // パス圧縮
    }
    return parent[vertex];
}

union関数の実装

union関数は、2つの頂点が属する集合を一つに統合し、サイクルの発生を防止する役割を担います。

以下はランクを利用した union 操作のサンプルコードです：

#include <stdio.h>
#include <stdlib.h>
void unionSets(int* parent, int* rank, int vertex1, int vertex2) {
    int root1 = find(parent, vertex1);
    int root2 = find(parent, vertex2);
    if (root1 == root2) return;
    // ランクが低い方を高い方に結合
    if (rank[root1] < rank[root2]) {
        parent[root1] = root2;
    } else if (rank[root1] > rank[root2]) {
        parent[root2] = root1;
    } else {
        parent[root2] = root1;
        rank[root1]++;
    }
}

コード例と各処理の解説

main関数の役割と構成

main関数は、クラスカル法の全体のフローをまとめ、以下の処理を順次実行する役割を果たします：

頂点数、辺数、各辺情報の入力
メモリの確保と初期化
辺のソート
Union-Findを利用したサイクル検出と MST の構築
結果の出力

実際の実装例では、各処理が関数として分割され、それぞれが連携する形で全体の処理が進むようになります。

以下は main関数のサンプルコードです：

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int from;
    int to;
    int weight;
} Edge;
int compareEdge(const void* a, const void* b) {
    Edge* edgeA = (Edge*)a;
    Edge* edgeB = (Edge*)b;
    return edgeA->weight - edgeB->weight;
}
int find(int* parent, int vertex) {
    if (parent[vertex] != vertex) {
        parent[vertex] = find(parent, parent[vertex]);  // パス圧縮
    }
    return parent[vertex];
}
void unionSets(int* parent, int* rank, int vertex1, int vertex2) {
    int root1 = find(parent, vertex1);
    int root2 = find(parent, vertex2);
    if (root1 == root2) return;
    if (rank[root1] < rank[root2]) {
        parent[root1] = root2;
    } else if (rank[root1] > rank[root2]) {
        parent[root2] = root1;
    } else {
        parent[root2] = root1;
        rank[root1]++;
    }
}
int main(void) {
    int numVertices, numEdges;
    // 頂点数と辺数を読み込み
    scanf("%d %d", &numVertices, &numEdges);
    // エッジ情報の配列を確保
    Edge* edges = (Edge*)malloc(numEdges * sizeof(Edge));
    if (edges == NULL) {
        printf("メモリ確保エラー\n");
        return 1;
    }
    // 各エッジの情報を入力
    for (int i = 0; i < numEdges; i++) {
        scanf("%d %d %d", &edges[i].from, &edges[i].to, &edges[i].weight);
    }
    // エッジのソート
    qsort(edges, numEdges, sizeof(Edge), compareEdge);
    // Union-Find 用の配列を初期化
    int* parent = (int*)malloc(numVertices * sizeof(int));
    int* rank = (int*)malloc(numVertices * sizeof(int));
    if (parent == NULL || rank == NULL) {
        printf("メモリ確保エラー\n");
        return 1;
    }
    for (int i = 0; i < numVertices; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
    // MSTの構築
    int mstWeight = 0;
    for (int i = 0; i < numEdges; i++) {
        int root1 = find(parent, edges[i].from);
        int root2 = find(parent, edges[i].to);
        if (root1 != root2) {  // サイクルが形成されなければ採用
            mstWeight += edges[i].weight;
            unionSets(parent, rank, root1, root2);
        }
    }
    printf("最小全域木の重み: %d\n", mstWeight);
    free(edges);
    free(parent);
    free(rank);
    return 0;
}

(入力に応じた最小全域木の合計重量が表示されます)

補助関数の連携と詳細

エラーチェックの工夫

各関数やメモリ確保処理において、エラーチェックをしっかり行うことが大切です。

例えば、malloc の返り値が NULL であるかどうかのチェックを行い、必要な場合はエラーメッセージを出力することで、予期しないクラッシュを防止する工夫を取り入れています。

また、入力データの検証も行うことで、不正なデータに対する対策を講じるとよいでしょう。

デバッグ時の注意点

実装中は以下の点に注意してデバッグを進めると良いです：

各関数の戻り値を確認し、正しい値が返っているかを検証する
メモリ確保後や配列のアクセス範囲に注意し、不正なアクセスが無いかをチェックする
ソート処理やUnion-Findの動作について、各ステップごとに変数の状態を出力するなどして、アルゴリズムが正しく動作しているか確認する

これらの工夫により、実装の信頼性を高め、後からのバグ修正を容易に行えるようなコードを書くことができます。

まとめ

この記事では、クラスカル法による最小全域木(MST)の生成方法について解説しています。

MSTの定義と目的、貪欲アルゴリズムの基本的な仕組み、Union-Find構造によるサイクル検出の方法が理解できます。

また、C言語における具体的なデータ構造の定義、グラフ入力・初期化、辺のソート、Union-Findの操作を丁寧に説明し、サンプルコードも示すことで実践的な実装例が確認できる内容となっています。