[Java] Kruskal 알고리즘

MST를 찾는 알고리즘입니다.

(설명을 잘 못해서 코드를 보시는 게 빠를 수 있습니다.... ㅠ)

 

1. 간선의 정보가 E개가 들어온다면 E개의 시작점, 도착점, 가중치를 저장할 수 있는 Edge 객체 배열을 만들고 저장하였습니다.

다음으로, 크루스칼 알고리즘은 그리디 알고리즘을 적용하고 있기 때문에 가중치를 기준으로 Edge 배열을 정렬하여 가장 낮은 가중치를 갖고 있는 간선의 정보를 우선적으로 처리하게 했습니다.

 

2. make() 함수를 이용해서 자기 자신이 부모가 되게 parents 배열을 초기화하는 작업을 하였습니다.

 

3. Edge 배열에 든 Edge들을 하나씩 처리하면서 union()을 처리하게 했습니다.

union()은 최상위 부모 정점을 찾아주는 findSet을 통해 aRoot와 bRoot를 구했습니다.

이때, findSet은 최상위 부모 정점만 가질 수 있도록 path compression을 적용했습니다.

다음으로, 연결하고자 하는 두 정점의 부모가 같다면 즉, aRoot와 bRoot가 같다면 이미 연결돼있는 점이므로 false를 반환하고 아니라면 rank를 적용하여 rank가 큰 부모에게 연결되게 하고 true를 반환하게 했습니다.

이때, true일 경우 해당 Edge의 weight를 정답에 더해 MST의 값을 구하게 했습니다.

마지막으로 Edge 배열을 순회하면서 union이 가능할 때 cnt를 세어 만약 정점의 개수 -1 즉, V - 1과 같은 수가 된다면 모든 점을 연결하게 된 것이므로 더 이상 볼 필요가 없으므로 break를 사용하여 결과를 출력하도록 만들었습니다.

---

코드

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

public class Kruscal {
	public static class Edge implements Comparable<Edge> {
		int from, to, weight;
		
		public Edge(int from, int to, int weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.weight, o.weight);
		}
	}
	
	public static int V, E;
	public static int[] parents, rank;
	public static Edge[] edge;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		parents = new int[V + 1];
		rank = new int[V + 1];
		edge = new Edge[E];
		
		for (int i = 0; i < E; ++i) {
			st = new StringTokenizer(br.readLine(), " ");
			
			edge[i] = new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		
		Arrays.sort(edge);
		
		make();
		
		int result = 0;
		int cnt = 0;
		
		for (Edge e : edge) {
			if (union(e.from, e.to) ) {
				result += e.weight;
				
				if (++cnt == V - 1) {
					break;
				}
			}
		}
		
		System.out.println(result);
	}
	
	public static void make() {
		for (int i = 1; i <= V; ++i) {
			parents[i] = i;
		}
	}
	
	public static int findSet(int a) {
		if (parents[a] == a) {
			return a;
		}
		
		return parents[a] = findSet(parents[a]);
	}
	
	public static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		
		if (aRoot == bRoot) {
			return false;
		}
		
		if (rank[aRoot] < rank[bRoot]) {
			parents[aRoot] = bRoot;
		}
		else {
			parents[bRoot] = aRoot;
			
			if (rank[aRoot] == rank[bRoot]) {
				rank[aRoot]++;
			}
		}
		
		return true;
	}
}