ヽ｜∵｜ゝ(Fantom) の 開発blog？

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;
        }
    }
}

・・・（略）・・・
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;
    }
    ・・・（略）・・・
}

/**<h1>素集合データ構造 (Disjoint Set Forest)</h1>
 * <p>互いに素な集合。
 * <br>内部的には配列で定義されている。</p>
 */
public class UnionFindTree {

    private int[] parent;    //親ノード
    private int[] rank;      //高さ or 次数

    /**<h1>コンストラクタ</h1>
     * <p></p>
     * @param size ： ノード数
     */
    public UnionFindTree(int size) {
        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < size; i++) {
            makeSet(i);
        }
    }

    /**<h1>ノードを作成する</h1>
     * <p>作成されたノードはルートとなる。
     * <br>元のサイズより大きいノードを指定した場合エラー。</p>
     * @param x ： ノード
     */
    public void makeSet(int x) {
        parent[x] = x;
        rank[x] = 0;
    }

    /**<h1>x, y の属している木を結合する</h1>
     * <p>同じ木の場合は何もしない。</p>
     * @param x ： ノード1
     * @param y ： ノード2
     */
    public void union(int x, int y) {
        final int xRoot = find(x);
        final int yRoot = find(y);

        if (rank[xRoot] > rank[yRoot]) {
            parent[yRoot] = xRoot;        //x の木に結合
        }
        else if(rank[xRoot] < rank[yRoot]) {
            parent[xRoot] = yRoot;        //y の木に結合
        }
        else if (xRoot != yRoot) {        //同じ高さで根が違うとき
            parent[yRoot] = xRoot;        //x の木に結合
            rank[xRoot]++;                //x の木の高さを加算
        }
    }

    /**<h1>属している木のルートを返す</h1>
     * <p>検索したノードは経路圧縮が行われる。</p>
     * @param x ： ノード
     * @return<b>int</b> ： ルートのノード
     */
    public int find(int x) {
        if (x != parent[x]) {    //根でないとき
            parent[x] = find(parent[x]);    //直接、根に繋ぐ(経路圧縮)
        }
        return parent[x];
    }

    /**<h1>同じ木に属しているかどうかを返す</h1>
     * <p>同じルートを持っているかで判別する。</p>
     * @param x ： ノード1
     * @param y ： ノード2
     * @return<b>boolean</b> ： true = 同じ木に属している
     */
    public boolean same(int x, int y) {
        return find(x) == find(y);
    }
}

void link(int x, int y) {
    if (rank[x] > rank[y]) {
        p[y] = x;
    } else {
        p[x] = y;
        if (rank[x] == rank[y]) {
            rank[y]++;
        }
    }
}

import java.util.LinkedList;
import java.util.List;

/**<h1>素集合データ構造 (Disjoint Set)</h1>
 * <p>互いに素な集合。
 * <br>内部的には LinkedList で定義されている。</p>
 */
public class UnionFindTreeList {

    private List<Integer> parent = new LinkedList<Integer>();    //親ノード
    private List<Integer> rank = new LinkedList<Integer>();      //高さ or 次数

    //コンストラクタ
    /**<h1>空のコンストラクタ</h1>
     * <p>newSet() でノードを新規追加する。</p>
     */
    public UnionFindTreeList() {
    }

    /**<h1>ノード数指定のコンストラクタ</h1>
     * <p>予めノードを生成する。</p>
     * @param size ： ノード数
     */
    public UnionFindTreeList(int size) {
        for (int i = 0; i < size; i++) {
            parent.add(i);
            rank.add(0);
        }
    }

    /**<h1>ノードを新規に追加する。</h1>
     * <p>最後に追加され、ルートとなる。</p>
     * @return<b>int</b> ： 追加されたノード
     */
    public int newSet() {
        final int x = parent.size();
        parent.add(x);
        rank.add(0);
        return x;
    }

    /**<h1>ノードを作成する</h1>
     * <p>作成されたノードはルートとなる。
     * <br>元のサイズより大きいノードを指定した場合エラー。</p>
     * @param x ： ノード
     */
    public void makeSet(int x) {
        parent.set(x, x);
        rank.set(x, 0);
    }

    /**<h1>x, y の属している木を結合する</h1>
     * <p>同じ木の場合は何もしない。</p>
     * @param x ： ノード1
     * @param y ： ノード2
     */
    public void union(int x, int y) {
        final int xRoot = find(x);
        final int yRoot = find(y);

        if (rank.get(xRoot) > rank.get(yRoot)) {
            parent.set(yRoot, xRoot);    //x の木に結合
        }
        else if(rank.get(xRoot) < rank.get(yRoot)) {
            parent.set(xRoot, yRoot);    //y の木に結合
        }
        else if (xRoot != yRoot) {        //同じ高さで根が違うとき
            parent.set(yRoot, xRoot);    //x の木に結合
            rank.set(xRoot, rank.get(xRoot) + 1);    //x の木の高さを加算
        }
    }

    /**<h1>属している木のルートを返す</h1>
     * <p>検索したノードは経路圧縮が行われる。</p>
     * @param x ： ノード
     * @return<b>int</b> ： ルートのノード
     */
    public int find(int x) {
        if (x != parent.get(x)) {    //根でないとき
            parent.set(x, find(parent.get(x)));    //直接、根に繋ぐ(経路圧縮)
        }
        return parent.get(x);
    }

    /**<h1>同じ木に属しているかどうかを返す</h1>
     * <p>同じルートを持っているかで判別する。</p>
     * @param x ： ノード1
     * @param y ： ノード2
     * @return<b>boolean</b> ： true = 同じ木に属している
     */
    public boolean same(int x, int y) {
        return find(x) == find(y);
    }

    /**<h1>全ノードを消去</h1>
     * <p>内部の LinkedList をクリアする。</p>
     */
    public void clear() {
        parent.clear();
        rank.clear();
    }
}