ヽ|∵|ゝ(Fantom) の 開発blog? ホーム »データ構造
このページの記事一覧

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


 クラスカル法最小全域木を求めるアルゴリズムである。解説などは 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プログラマのためのアルゴリズムとデータ構造」よりも、図解やサンプルコードが多くてわかりやすい。同じようなタイトルはいくつも出ているので、1冊くらい読んでみると役に立つかも知れない。最近では Wikipedia みたいなネット事典でも手軽に見れるようになったので、他の資料と合わせて、色々検証してみると理解が深まりやすい。


(関連記事)
【Java】プリム法[最小全域木] (Prim's algorithm, Minimum Spannig Tree)
【Java】素集合データ構造[互いに素な集合] (Union Find Tree, Disjoint Set Forest)
【Java】ダイクストラ法[単一始点最短経路] (Dijkstra's algorithm, Single Source Shortest Path)
【Java】ベルマン-フォード法[単一始点最短経路] (Bellman-Ford algorithm, Single Source Shortest Path)
【Java】ワーシャル-フロイド法[全点対間最短経路] (Warshall-Floyd algorithm, All Pairs Shortest Path)


■参考になる書籍


スポンサーサイト

category: Java

thread: プログラミング

janre: コンピュータ

tag: 最短経路  アルゴリズム  データ構造 
tb: 0   cm: --

【Java】素集合データ構造[互いに素な集合] (Union Find Tree, Disjoint Set Forest)  


 また例によって色々な本を見ているのだが、今回はプログラミングコンテスト攻略のためのアルゴリズムとデータ構造という本の P.322~323 に載っている(C++ 版)「互いに素な集合」(Union Find, Disjoint Set)で少しだけ疑問に思った所があったので分析してみたら、微妙なバグ(?)を見つけた。


 といっても答えは間違ってないので、動作的には問題ない。正誤表にも載ってないね。検索してもそもそもあまり日本語サイトすら出てこなかったので、いつものように Wikipedia を見ながら簡単なものを作ってみた。といってもクラス(本では DisjointSet)部分をそのまま作りなおしたという感じだけどね。

●静的配列版 UnionFindTree
/**<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);
}
}

 内部的には静的配列でノードを定義しているが、LinkedList あたりにして、動的配列にするのもいいかもね。アルゴリズムそのままなので、「UnionFindTree」か「DisjointSet」でググれば同じようなものが一杯出てくると思うが、まぁ、英語でコメント書かれているものばかりなので、こちらを勉強用にする分には役に立つだろう。

 書籍で気になったのは以下の部分だ。
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]++;
}
}
}

 これは木を結合する処理だが、入れ子になっている条件分岐をよく見てみると、x, y が元々同じ木だったとき、「rank[x] == rank[y]」の条件に当てはまり、無駄にrankが増える。例題では問題ないし(同じ木のものは結合してない)、答えも正しく出るのだが、まぁ、テストケースによっては危うくなるかも知れない(データ上は rank が大きいが実際には小さかったりすると、正しく木の大きさを評価できないわけで…)。


 ついでなので、以下は内部データを LinkedList にしてみたもの。ほぼ機械的に書き換えてみただけ。後からノードを追加できるメリットがある。

●LinkedList 版 UnionFindTree
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();
}
}

 newSet() と clear() は勝手に作ったメソッドだが、連番のノード追加と全消去しかできない。データ型も Integer で固定しているが、Longジェネリクス型にしても良いだろう。しかしそのときはループ変数なども変更しなければならないかも知れない。

 オーダーは O(log n) なので大量にデータがあるときには良いね。複雑な迷路の経路判定とか。

 まぁ、データ構造は使えれば高速化できるものが多いので、知っていても損はないだろう。


(関連記事)
【Java】クラスカル法[最小全域木] (Kruskal's algorithm, Minimum Spannig Tree)
【Java】プリム法[最小全域木] (Prim's algorithm, Minimum Spannig Tree)
【Java】ダイクストラ法[単一始点最短経路] (Dijkstra's algorithm, Single Source Shortest Path)
【Java】ベルマン-フォード法[単一始点最短経路] (Bellman-Ford algorithm, Single Source Shortest Path)
【Java】ワーシャル-フロイド法[全点対間最短経路] (Warshall-Floyd algorithm, All Pairs Shortest Path)


■参考になる書籍


category: Java

thread: プログラミング

janre: コンピュータ

tag: アルゴリズム  データ構造 
tb: 0   cm: --


プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop