【Java】プリム法[最小全域木] (Prim's algorithm, Minimum Spannig Tree)

ヽ｜∵｜ゝ(Fantom) の開発blog？ホーム » Java »【Java】プリム法[最小全域木] (Prim's algorithm, Minimum Spannig Tree)

【Java】プリム法[最小全域木] (Prim's algorithm, Minimum Spannig Tree)

2015/06/03 Wed [edit]

　前回のついでに、クラスカル法と同様、最小全域木を求めるアルゴリズムとしてプリム法というアルゴリズムがある。解説などは Wikipedia や他のホームページなどに譲るとして、前回と比較するために、同じ例を使って書いてみる。

●プリム法[最小全域木] Prim

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

public class Prim {

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

    public Prim() {
        //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

        //隣接リスト
        @SuppressWarnings("unchecked")
        List<Edge>[] edges = new List[n];
        for (int i = 0; i < n; i++) {
            edges[i] = new ArrayList<Edge>();
        }

        for (int i = 0; i < adj.length; i++) {
            edges[adj[i][0]].add(new Edge(adj[i][0], adj[i][1], adj[i][2]));
            edges[adj[i][1]].add(new Edge(adj[i][1], adj[i][0], adj[i][2])); //無向グラフなので、逆方向も接続する
        }

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

    //プリム法[最小全域木(Minimum Spannig Tree)]
    int prim(int n, List<Edge>[] edges) {
        boolean[] done = new boolean[n];    //訪問フラグ

        Queue<Edge> q = new PriorityQueue<Edge>();
        q.add(new Edge(0, 0, 0));     //０から(ダミー)

        int totalCost = 0;            //最小全域木の重み
        while (!q.isEmpty()) {
            Edge e = q.poll();        //最小コストの辺を取り出す
            if (done[e.target]) {
                continue;
            }

            done[e.target] = true;        //訪問済にする
            totalCost += e.cost;
            q.addAll(edges[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;
        }
    }
}

　隣接リストは List<Edge>[] のように List の配列で作っている。List のリスト（List<List<Edge>>）でも良いが、頂点数が固定なら、この方が簡潔だろう。「@SuppressWarnings("unchecked")」は警告を消しているだけなので、無くても動く。

　優先度付きキュー(PriorityQueue)には一番始めにダミーを入れているが、最小全域木はどこから始めても同じなので、０(頂点)以外でも良い（その場合は Edge の source と target は同じにして、cost は 0 にする）。

　頂点から伸びている辺のリストは、無造作にキューに入れてしまっているが、訪問(done)し終わった頂点は不要なので、キューに入れる前に、はじいても良い。辺が大量にあるデータなら少しは速くなるかも知れない（この例では簡単にするため、一気にすべて突っ込んでいる）。

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

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

●プリム法で選択した辺を返す版

・・・（略）・・・
import java.util.LinkedList;

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

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

        //選択した辺(確認)
        int len = paths.size();
        for (int i = 1; i < len; i++) {    //一番最初[0]はダミーのためスキップ
            System.out.println(paths.get(i));
        }
    }

    //プリム法[最小全域木(Minimum Spannig Tree)]
    //選択した辺を返す
    int prim(int n, List<Edge>[] edges, List<Edge> paths) {
        boolean[] done = new boolean[n];    //訪問フラグ

        Queue q = new PriorityQueue();
        q.add(new Edge(0, 0, 0));     //０から(ダミー)

        paths.clear();
        int totalCost = 0;            //最小全域木の重み
        while (!q.isEmpty()) {
            Edge e = q.poll();        //最小コストの辺を取り出す
            if (done[e.target]) {
                continue;
            }

            done[e.target] = true;        //訪問済にする
            totalCost += e.cost;
            paths.add(e);                 //選択した辺を記録(一番最初はダミー)
            q.addAll(edges[e.target]);    //隣接しているすべての辺を追加
        }

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