「minimum spanning tree」の編集履歴（バックアップ）一覧はこちら

「minimum spanning tree」(2013/10/09 (水) 11:51:29) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

-Prim法(隣接行列)
#highlight(java){{
final int INF = Integer.MAX_VALUE/2;
int[][] cost;

int prim() {
	int n = cost.length;
	int[] mincost = new int[n];
	boolean[] used = new boolean[n];
	Arrays.fill(mincost, INF);
	
	mincost[0] = 0;
	int res = 0;
	
	while (true) {
		int v = -1;
		for (int u = 0; u < n; u++) {
			if (!used[u] && (v == -1 || mincost[u] < mincost[v]))
				v = u;
		}
		
		if (v == -1) break;
		used[v] = true;
		res += mincost[v];
		
		for (int u = 0; u < n; u++) {
			mincost[u] = Math.min(mincost[u], cost[v][u]);
		}
	}
	
	return res;
}
}}


-Prim法(隣接リスト)
#highlight(java){{
class Edge {
	int to;
	int cost;
	Edge(int to, int cost) {
		this.to = to;
		this.cost = cost;
	}
}

class Pair implements Comparable<Pair> {
	int index;
	int cost;
	Pair(int i, int c) {
		index = i;
		cost = c;
	}
	@Override
	public int compareTo(Pair o) {
		return cost - o.cost;
	}
}

final int INF = Integer.MAX_VALUE/2;
List<Edge>[] list;

int prim() {
	int n = list.length;
	int[] mincost = new int[n];
	Arrays.fill(mincost, INF);
	mincost[0] = 0;
	Queue<Pair> queue = new PriorityQueue<Pair>();
	queue.add(new Pair(0, 0));
	int res = 0;
	
	while (!queue.isEmpty()) {
		Pair p = queue.poll();
		int v = p.index, c = p.cost;
		if (mincost[v] < c) continue;
		res += mincost[v];
		for (Edge e : list[v]) {
			if (mincost[e.to] > e.cost) {
				mincost[e.to] = e.cost;
				queue.add(new Pair(e.to, e.cost));
			}
		}
	}
	
	return res;
}
}}

-Prim法(隣接行列)
#highlight(java){{
final int INF = Integer.MAX_VALUE/2;
int[][] cost;

int prim() {
	int n = cost.length;
	int[] mincost = new int[n];
	boolean[] used = new boolean[n];
	Arrays.fill(mincost, INF);
	
	mincost[0] = 0;
	int res = 0;
	
	while (true) {
		int v = -1;
		for (int u = 0; u < n; u++) {
			if (!used[u] && (v == -1 || mincost[u] < mincost[v]))
				v = u;
		}
		
		if (v == -1) break;
		used[v] = true;
		res += mincost[v];
		
		for (int u = 0; u < n; u++) {
			mincost[u] = Math.min(mincost[u], cost[v][u]);
		}
	}
	
	return res;
}
}}


-Prim法(隣接リスト)
#highlight(java){{
class Edge {
	int to;
	int cost;
	Edge(int to, int cost) {
		this.to = to;
		this.cost = cost;
	}
}

class Pair implements Comparable<Pair> {
	int index;
	int cost;
	Pair(int i, int c) {
		index = i;
		cost = c;
	}
	@Override
	public int compareTo(Pair o) {
		return cost - o.cost;
	}
}

final int INF = Integer.MAX_VALUE/2;
List<Edge>[] list;

int prim() {
	int n = list.length;
	int[] mincost = new int[n];
	Arrays.fill(mincost, INF);
	mincost[0] = 0;
	Queue<Pair> queue = new PriorityQueue<Pair>();
	queue.add(new Pair(0, 0));
	int res = 0;
	
	while (!queue.isEmpty()) {
		Pair p = queue.poll();
		int v = p.index, c = p.cost;
		if (mincost[v] < c) continue;
		res += mincost[v];
		for (Edge e : list[v]) {
			if (mincost[e.to] > e.cost) {
				mincost[e.to] = e.cost;
				queue.add(new Pair(e.to, e.cost));
			}
		}
	}
	
	return res;
}
}}

-Kruskal法
#highlight(java){{
class Edge implements Comparable<Edge> {
	int from;
	int to;
	int cost;
	Edge(int from, int to, int cost) {
		this.from = from;
		this.to = to;
		this.cost = cost;
	}
	@Override
	public int compareTo(Edge o) {
		return cost - o.cost;
	}
}

Edge[] edge;
int n;  //頂点数

int kruskal() {
	Arrays.sort(edge);
	UnionFind uf = new UnionFind(n);
	int res = 0;
	for (int i = 0; i < edge.length; i++) {
		Edge e = edge[i];
		if (!uf.same(e.from, e.to)) {
			uf.unite(e.from, e.to);
			res += e.cost;
		}
	}
	return res;
}
}}