minimum spanning tree - procom @ ウィキ

• Prim法(隣接行列)

  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法(隣接リスト)

  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法

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