【Java】クラスカル法[最小全域木] (Kruskal's algorithm, Minimum Spannig Tree)

ヽ｜∵｜ゝ(Fantom) の開発blog？ホーム » Java »【Java】クラスカル法[最小全域木] (Kruskal's algorithm, Minimum Spannig Tree)

【Java】クラスカル法[最小全域木] (Kruskal's algorithm, Minimum Spannig Tree)

2015/06/01 Mon [edit]

　クラスカル法は最小全域木を求めるアルゴリズムである。解説などは Wikipedia や他のホームページなどに譲るが、実は前回作った「Union Find Tree」を使うと簡単にできてしまうので、ちょっと書いてみる。

　擬似コードを見ると少し難しく感じるが、このアルゴリズムを超大雑把に言うと、辺の重みのリストから、重みの小さい順に取り出し、閉路を作らないように繋ぎ合わせていくと（ここで Union-Find を使う）、最終的に最小全域木ができるというものだ。

　今回も「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」という本(P.361～362) をベースに考えているが(元は C++ 版)、重みを小さい順に取り出す部分は、より簡潔にするため、優先度付きキュー(PriorityQueue)を使っている。もちろん書籍のようにリストを昇順ソートして、頭から順次取り出しでも良い。

　サンプル中の「UnionFindTree」クラスは前回作ったものをそのまま使う。

●クラスカル法[最小全域木] Kruskal

import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

//最小全域木（クラスカル法）
public class Kruskal {

    public static void main(String[] args) throws Exception {
        new Kruskal();
    }

    public Kruskal() {
        //Wikipedia の例(図)をデータにしたもの
        int n = 7;    //頂点数
        int[][] adj = new int[][]{
            //接続元ノード, 接続先ノード, 重み
            {0, 1, 7},
            {0, 3, 5},
            {1, 2, 8},
            {1, 3, 9},
            {1, 4, 7},
            {2, 4, 5},
            {3, 4, 15},
            {3, 5, 6},
            {4, 5, 8},
            {4, 6, 9},
            {5, 6, 11}
        };  //答えは 39

        List<Edge> edges = new LinkedList<Edge>();    //辺の情報
        for (int i = 0; i < adj.length; i++) {
            edges.add(new Edge(adj[i][0], adj[i][1], adj[i][2]));
        }

        int ans = kruskal(n, edges);
        System.out.println(ans);    //最小全域木の重み
    }

    //クラスカル法[最小全域木(Minimum Spannig Tree)]
    int kruskal(int n, List<Edge> edges) {
        UnionFindTree uft = new UnionFindTree(n);  //閉路判定用
        Queue<Edge> q = new PriorityQueue<Edge>(edges);

        int totalCost = 0;        //最小全域木の重み
        while (!q.isEmpty()) {
            Edge e = q.poll();
            if (!uft.same(e.source, e.target)) {
                totalCost += e.cost;
                uft.union(e.source, e.target);
            }
        }

        return totalCost;
    }

    //辺情報の構造体
    class Edge implements Comparable<Edge> {
        public int source = 0;    //接続元ノード
        public int target = 0;    //接続先ノード
        public int cost = 0;      //重み

        public Edge(int source, int target, int cost) {
            this.source = source;
            this.target = target;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }

        @Override
        public String toString() {  //デバッグ用
            return "source = " + source + ", target = " + target + ", cost = " + cost;
        }
    }
}

　優先度付きキュー(PriorityQueue)の順番は辺情報の構造体（Edge）に Comparable インタフェースを噛ませて、コストを比較しているが、PriorityQueue のコンストラクタに Comparator を匿名クラスで定義しても良いだろう。そうすれば優先順位は色々変更できる。

　この例では戻値は最小全域木の総コストを返しているが、選択した辺を知りたければ、少し改造して辺のリストを記録すれば良い。

●クラスカル法で選択した辺を返す版

・・・（略）・・・
public class Kruskal {
    ・・・（略）・・・
    public Kruskal() {
        ・・・（略）・・・
        List<Edge> paths = new LinkedList<Edge>();    //選択した辺(戻値用)

        int ans = kruskal(n, edges, paths);
        System.out.println(ans);    //最小全域木の重み

        //選択した辺
        for (Edge e : paths) {
            System.out.println(e);
        }
    }

    //クラスカル法[最小全域木(Minimum Spannig Tree)]
    //選択した辺を返す
    int kruskal(int n, List<Edge> edges, List<Edge> paths) {
        UnionFindTree uft = new UnionFindTree(n);    //閉路判定用
        Queue<Edge> q = new PriorityQueue<Edge>(edges);

        paths.clear();
        int totalCost = 0;        //最小全域木の重み
        while (!q.isEmpty()) {
            Edge e = q.poll();
            if (!uft.same(e.source, e.target)) {
                totalCost += e.cost;
                uft.union(e.source, e.target);
                paths.add(e);    //選択した辺を記録
            }
        }

        return totalCost;
    }
    ・・・（略）・・・
}

　コストを時間と考えて、路線図みたいなものの最小全域木(最短経路)を求めるのに良いかもね。アルゴリズムを利用するには「何に使えるか？」を想像してみると覚えやすくなるかも知れない。

　最近よくアルゴリズムを検索しているが、高度なものになるほど、ほとんどが海外ページだったりするので、書籍を参考にするのも良いかもね。ただし本は C や C++ 版が多いけどね。ネット上だと Ruby や Python が多い気がする。「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」(C,C++)は、昔読んだ「定本 Cプログラマのためのアルゴリズムとデータ構造」よりも、図解やサンプルコードが多くてわかりやすい。同じようなタイトルはいくつも出ているので、１冊くらい読んでみると役に立つかも知れない。最近では Wikipedia みたいなネット事典でも手軽に見れるようになったので、他の資料と合わせて、色々検証してみると理解が深まりやすい。