[Theory] Graph 4. MST - KRUSKAL

 

    KRUSKAL 알고리즘은 간선을 하나씩 선택해서 MST(Minimun Spanning Tree) 를 찾는 과정이다. 여기서 MST(Minimum Spanning Tree)는 우리말로 '최소 신장 트리' 라고 하는데, 무향 가중치 그래프에서 신장트리를 구성하는 가중치의 합이 최소인 트리를 말한다. 더불어 신장트리(Spanning Tree)라는 것은 무향 그래프에서 n개의 정점과, n-1개의 간선으로 이루어진 트리를 말한다. 

알고리즘의 동작과정을 요약하면 다음과 같다.

1. 모든 간선을 가중치에 따라 오름차순으로 정렬한다. (Sort)
2. 가중치가 낮은 간선부터 골라 트리를 만든다 ( 이때 사이클이 발생하면 다음으로 낮은 간선을 선택한다 )
3. n-1개의 간선을 고를때 까지 반복한다. 

이번엔 그림으로 살펴보자.

  주의할 점은 스패닝 트리에서 사이클이 발생하는 경우이다. (어짜피 사이클이 발생하는 순간 더이상 트리가 아니지만 아무튼;;) 마지막 그림으로 넘어가는 직전 지점이 생략되어 있으므로 상상해 보자 보자. 바로 직전을 예상해 보면서 그 다음 작은 가중치를 가지는 간선은 6이다. 하지만 6을 선택하는 순간 트리에는 사이클이 생긴다. 따라서 그 다음 가중치인 8을 선택하여 스패닝 트리를 완성한 모습이다. 

[ 동작과정 ] 

Point 1. edge Sorting

Arrays.sort(edgeList);

 

Point 2.  사이클 체크 (Union-Find)

사이클 체크는 Union-Find에서 사용했던 코드를 그대로 사용하면 된다. Edge의 from과 to 각각의 부모노드가 같다는 말은 결국 사이클이라는 의미이다.

static int findSet(int a) {
	if(parents[a]==a) { 
		return a;
	}
	return parents[a] = findSet(parents[a]); 
}
	
static boolean union(int a, int b) {
	int aRoot = findSet(a);
	int bRoot = findSet(b);
	if(aRoot == bRoot) return false;
		
	parents[bRoot]= aRoot;
	return true;
}

 

- 전체 코드

package com.ssafy.disjointset;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class MST1_Kruskal {
	
	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 (this.weight-o.weight);
			return Integer.compare(this.weight, o.weight);
		}
	}
	
	static int V,E; // 정점개수, 간선개수
	static int parents[];
	static Edge[] edgeList;
	
	static void make() { // 크기가 1인 단위집합을 만든다.
		for(int i=0; i<V; i++) {
			parents[i] = i;
		}
	}
	
	static int findSet(int a) {
		if(parents[a]==a) { 
			return a;
		}
		return parents[a] = findSet(parents[a]); 
	}
	
	static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if(aRoot == bRoot) return false;
		
		parents[bRoot]= aRoot;
		return true;
	}
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		parents = new int[V];
		edgeList = new Edge[E];
		
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			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);
		}
		// 1. 간선리스트 가중치 기준 오름차순 정렬
		Arrays.sort(edgeList);
		
		make();
		int result =0;
		int count = 0; // 선택한 간선수
		
		for (Edge edge : edgeList) {
			if(union(edge.from, edge.to)) { // 싸이클이 발생하지 않았다면
				result += edge.weight;
				if(count++ == V-1) break;
			}
		}
		System.out.println(result);
	}

}