JavaScriptで実装するクラスカルのアルゴリズム｜Union-Findで最小全域木を求める

クラスカル法（Kruskal's algorithm）は、グラフから最小全域木を求めるための貪欲アルゴリズムです。このアルゴリズムは、以下の手順で動作します。

1. グラフ内のすべての辺を集合として作成します。
2. 集合が空でなく、かつすべての頂点がカバーされていない間、以下を繰り返します。
   • 集合から重みが最小の辺を取り出します。
   • その辺がサイクルを形成するか、あるいは単に2つの木をつなぐだけかを判定します。サイクルを形成する場合はその辺を破棄し、そうでなければ木に追加します。
3. 処理が完了すると、最小全域木が完成します。

必要な補助データ構造

このアルゴリズムを実装するには、さらに2つのデータ構造が必要になります。

1つ目は優先度付きキュー（Priority Queue）です。辺を重み順にソートした状態で保持し、各反復で必要な最小の辺を効率よく取り出すために使用します。

2つ目は素集合データ構造（Disjoint Set / Union-Find）です。これは、要素の集合を互いに重なり合わない複数の部分集合に分割して管理するデータ構造です。新しいノードを木に追加する際に、そのノード同士がすでに連結済みかどうかを確認します。すでに連結していればサイクルが存在することになり、未連結であれば辺の両端の頂点を統合（union）して同じ部分集合に加えます。

Union-Find（DisjointSet）の実装例

class UnionFind {
    constructor(elements) {
        // 未連結な成分の数
        this.count = elements.length;

        // 連結成分を追跡するためのマップ
        this.parent = {};

        // 初期状態では、すべての要素自身が親になるよう設定
        elements.forEach(e => (this.parent[e] = e));
    }

    union(a, b) {
        let rootA = this.find(a);
        let rootB = this.find(b);

        // ルートが同じなら、すでに連結済み
        if (rootA === rootB) return;

        // 常に小さい方のルートを親にする
        if (rootA < rootB) {
            if (this.parent[b] != b) this.union(this.parent[b], a);
            this.parent[b] = this.parent[a];
        } else {
            if (this.parent[a] != a) this.union(this.parent[a], b);
            this.parent[a] = this.parent[b];
        }
    }

    // ノードの最終的な親（ルート）を返す
    find(a) {
        while (this.parent[a] !== a) {
            a = this.parent[a];
        }
        return a;
    }

    // 2つのノードが連結しているかどうかを判定
    connected(a, b) {
        return this.find(a) === this.find(b);
    }
}

このクラスは次のようにテストできます。

テストコード

let uf = new UnionFind(["A", "B", "C", "D", "E"]);
uf.union("A", "B"); uf.union("A", "C");
uf.union("C", "D");

console.log(uf.connected("B", "E"));
console.log(uf.connected("B", "D"));

実行結果

false
true

BとEはまだ統合されていないため false、BとDは同じ部分集合に属しているため true が出力されます。

クラスカル法による最小全域木の実装

続いて、このUnion-Findを使ってクラスカル法を実装してみましょう。

実装例

kruskalsMST() {
    // 最小全域木（MST）を格納するグラフを初期化
    const MST = new Graph();
    this.nodes.forEach(node => MST.addNode(node));
    if (this.nodes.length === 0) {
        return MST;
    }

    // 優先度付きキューを作成
    edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);

    // すべての辺をキューに追加
    for (let node in this.edges) {
        this.edges[node].forEach(edge => {
            edgeQueue.enqueue([node, edge.node], edge.weight);
        });
    }

    let uf = new UnionFind(this.nodes);

    // キューが空になるまでループ
    while (!edgeQueue.isEmpty()) {
        // 分割代入で辺のデータを取得
        let nextEdge = edgeQueue.dequeue();
        let nodes = nextEdge.data;
        let weight = nextEdge.priority;

        // サイクルを形成しない場合のみ、辺をMSTに追加
        if (!uf.connected(nodes[0], nodes[1])) {
            MST.addEdge(nodes[0], nodes[1], weight);
            uf.union(nodes[0], nodes[1]);
        }
    }
    return MST;
}

実際のグラフで動作を確認してみます。

テストコード

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");

g.addEdge("A", "C", 100);
g.addEdge("A", "B", 3);
g.addEdge("A", "D", 4);
g.addEdge("C", "D", 3);
g.addEdge("D", "E", 8);
g.addEdge("E", "F", 10);
g.addEdge("B", "G", 9);
g.addEdge("E", "G", 50);

g.kruskalsMST().display();

実行結果

A->B, D
B->A, G
C->D
D->C, A, E
E->D, F
F->E
G->B

重み100の辺「A-C」や重み50の辺「E-G」など、サイクルを形成する不要な辺が除外され、重みの小さい6本の辺だけで全体をカバーする最小全域木が正しく構築されていることが分かります。

計算量について

すべての辺を優先度付きキューに追加して処理するため、クラスカル法の計算量は O(E log E)（Eは辺の数）となります。Union-Findによるサイクル判定もほぼ定数時間で行えるため、大規模なグラフでも効率的に最小全域木を求められます。