Kruskal 알고리즘

신장 트리 (Spanning Tree)

n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리, 즉 그래프의 모든 정점을 가장 적은 개수의 간선으로 연결한 그래프

최소 신장 트리 (Minimum Spanning Tree)

모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 신장 트리, 최소 신장 트리를 만드는 대표적인 알고리즘에는 Prim 또는 Kruskal 알고리즘이 있다. 보통 최소 신장 트리를 줄여서 MST라고 부른다.

Kruskal 알고리즘

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

1-1. 간선 리스트를 만든다.

1-2. 만든 간선 리스트를 가중치 순으로 오름차순 정렬한다.

 

2. 간선을 하나씩 확인해 해당 간선이 사이클을 발생시키는지 확인 (초기 MST는 간선이 없고 정점만 있는 상태)

2-1. 사이클이 발생하는 경우 해당 간선을 MST에 포함시키지 않음

2-2. 사이클이 발생하지 않을 경우 간선을 MST에 포함

 

최소 신장 트리를 만들려면 E개의 간선 중 V-1개의 간선을 선택해야 한다. Kruskal 알고리즘의 아이디어는 최소 비용 순으로 간선을 선택하는데, 사이클이 발생시키는 간선은 제외시킨다는 그리디 방식의 아이디어다. Kruskal 알고리즘은 union-find 알고리즘을 사용하는데, 이는 MST내의 부분 그래프를 집합으로 표현하고 두 개의 부분 그래프가 연결될 때마다 합집합 연산을 수행하기 위함이다.

• 같은 부분 그래프의 두 정점을 연결하는 간선은 사이클을 발생시킴 → 두 개의 간선 정점이 같은 집합에 포함되어 있다면 해당 간선 제외 (find 연산 수행) 
• 서로 다른 부분 그래프의 두 정점을 연결하는 간선은 사이클이 발생하지 않음 → 간선을 MST에 포함시키고 합집합 연산 수행 (union 연산 수행)

kruskal 알고리즘의 시간 복잡도는 어떻게 될까. 먼저 간선 리스트를 정렬하므로 O(E log E)의 시간 복잡도가 든다. 그 후 최소 신장 트리를 만들기 위해 최대 E번의 union 연산을 수행하는데 union 연산의 시간 복잡도는 상수 시간이므로 최소 신장 트리를 만드는 시간 복잡도는 O(E)이다. 따라서 kruskal 알고리즘의 시간 복잡도는 O(E log E) 임을 알 수 있다.

 

아래는 Kruskal 알고리즘을 적용하는 백준 1197번 문제 "최소 스패닝 트리"의 코드이다.

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

/***
 * V(정점의 개수, 1 <= V <= 10000)
 * E(간선의 개수, 1 <= E <= 100000)
 * 간선의 정보(A, B, C) - (간선 정점 A,B | 가중치 C)
 * 
 * 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있음
 * 가중치 C는 음수일수도 있음
 */


public class Main {

	static class Edge {
		int v1;
		int v2;
		int weight;
		public Edge(int v1, int v2, int weight) {
			this.v1 = v1;
			this.v2 = v2;
			this.weight = weight;
		}
	}
	
	static int[] parent;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		int answer = 0;
		int select = 0;
		
		//간선 리스트 생성
		List<Edge> edgeList = new ArrayList<Edge>();
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			edgeList.add(new Edge(v1, v2, weight));
		}
		
		//union-find를 위한 parent 배열 생성
		parent = new int[N+1];
		for(int i=1; i<=N; i++) parent[i] = i;
		
		//간선 리스트 가중치 순 오름차순 정렬
		edgeList.sort((e1, e2) -> Integer.compare(e1.weight, e2.weight));
		
		//크루스컬 알고리즘 시작
		for(int i=0; i<E; i++) {
			
			//최적화, V-1개의 간선을 선택했으면 이후 간선을 선택할 필요가 없음
			if(select == N - 1) break;
			
			//탐욕적으로 간선 선택
			Edge edge = edgeList.get(i);
			
			if(!union(edge.v1, edge.v2)) continue;
			
			select++;
			answer += edge.weight;
		}
		
		System.out.println(answer);
	}
	
	static boolean union(int x, int y) {
		int rootX = find(x);
		int rootY = find(y);		
		if(rootX == rootY) return false;
		
		parent[rootY] = rootX;
		return true;
	}
	
	static int find(int x) {
		if(parent[x] == x) return x;
		
		parent[x] = find(parent[x]);
		return parent[x];
	}
}