[알고리즘] Kruskal's 알고리즘

Kruskal's 알고리즘

탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

• 탐욕적인 방법
  • 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것
  • 탐욕적인 방법은 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야 한다.
  • 다행히 Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다.
• MST(최소 비용 신장 트리) 가 1) 최소 비용의 간선으로 구성됨 2) 사이클을 포함하지 않음 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 한다.

알고리즘 동작

1. 간선 리스트 작성

2. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬

3. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴

   • 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택

4. n-1개의 간선이 선택될 때까지 2번 반복

코드

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

public class MST1_KruskalTest {
	
	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) {
			// Integer.compare(this.weight, o.weight);	// 가중치에 음수가 포함된 경우 
			return 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 findSet(parents[a]);					// path compression 전
		return parents[a] = findSet(parents[a]);	// path compression 후
	}
	
	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 e : edgeList) {
			if(union(e.from, e.to)) {
				result += e.weight;
				if(++count == V-1) break;
			}
		}
		
		System.out.println(result);
	}

}