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

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


 前回のついでに、クラスカル法と同様、最小全域木を求めるアルゴリズムとしてプリム法というアルゴリズムがある。解説などは 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)); //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)には一番始めにダミーを入れているが、最小全域木はどこから始めても同じなので、0(頂点)以外でも良い(その場合は 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)); //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;
}
・・・(略)・・・
}

 辺のリストの [0] はダミーになるので、List.remove(0) で除去しても良い。

 隣接行列を使ったり、優先度付きキュー(PriorityQueue)を使わずに、配列に最小コストを記録していく方法もあるが、かえって難しい気がする。色々やってみると良いだろう。





(関連記事)
【Java】クラスカル法[最小全域木] (Kruskal'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: --


トラックバック

トラックバックURL
→http://fantom1x.blog130.fc2.com/tb.php/177-b36979cc
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR