[Java] 크루스칼 알고리즘

크루스칼 알고리즘 베이스 코드 입니다.

 

• 크루스칼 알고리즘: 간선들을 기준으로 MST를 찾는 알고리즘
• 최소 신장 트리(MST): 간선들의 가중치의 합이 최소인 신장 트리이다.

 

절차

1. 모든 간선을 가중치에 따라 오름차순으로 정렬
2. 가중치가 가장 낮은 간선 부터 추가
3. 사이클이 생기면 간선 pass
4. n-1개의 간선이 선택되면 중지

특징

• 정점 대비 간선 수가 많은 형태를 보이는 그래프에서는 크루스칼이 불리하다.
• 그럴때는 프림이 유리하다.

import java.io.*;
import java.util.*;

public class MST_Kruskal {
	
	static class Edge implements Comparable<Edge>{
		int from, to, weight;

		public Edge(int from, int to, int weight) {
			super();
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return this.weight - o.weight;
		}
	}
	
	static Edge[] edgeList;
	static int[] parents;
	static int[] rank;
	
	static int V, E;
	
	static void make() {
		parents = new int[V];
		rank = new int[V];
		for(int i=0; i<V; i++) {
			parents[i] = i;
		}
	}
	
	static int find(int a) {
		if(a==parents[a]) {
			return a;
		}
		
		return parents[a] = find(parents[a]);
	}
	
	static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		
		if(aRoot == bRoot) {
			return false;
		}
		
		if(rank[aRoot] > rank[bRoot]) {
			parents[bRoot] = aRoot;
		} else if(rank[aRoot] < rank[bRoot]) {
			parents[aRoot] = bRoot; 
		} else {
			parents[bRoot] = aRoot;
			rank[aRoot]++;
		}
		return true;
	}
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine().trim());
		
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		edgeList = new Edge[E];
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(in.readLine().trim());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			edgeList[i] = new Edge(from, to, weight);
		}
		
		Arrays.sort(edgeList);
		make(); // V개의 독립된 트리 생성
		int result=0, count = 0;
		
		for(Edge edge : edgeList) {
			if(union(edge.from, edge.to)) { // 두 정점이 속한 트리를 합침 
				result += edge.weight;
				if(++count == V-1) {
					break;
				}
			}
		}
		System.out.println(result);
	}
}


/*
5 10
0 1 5
0 2 10
0 3 8
0 4 7
1 2 5
1 3 3
1 4 6
2 3 1
2 4 3
3 4 1

output==>10

7 11
0 1 32
0 2 31
0 5 60
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51

output==>175
*/