minimum spanning tree


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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