크루스칼 알고리즘 (Kruskal's Algorithm)

크루스칼 알고리즘 (Kruskal's Algorithm)

크루스칼 알고리즘은 여러개의 Spanning Tree 중 최소 비용을 가지는 Tree를 구하는 알고리즘이다.

주로 간선의 방향성이 없고, 모든 노드를 방문해야 하며, 간선에 가중치가 주어질 때 주로 사용된다.

이러한 최소비용을 가지는 Spanning Tree를 MST(Minimum Cost Spanning Tree), 최소비용신장트리라고 한다.

MST 문제를 해결하기 위한 알고리즘으로는 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 있다.

크루스칼 알고리즘은 Merge Sort와 Union-Find를 사용하여 구현한 알고리즘이고,

프림 알고리즘은 Heap을 사용하여 구현하는 알고리즘이다.

우선 Spanning Tree(신장트리)가 무엇인지 알아보자.

Spanning Tree ?

신장트리란 연결 부분 그래프 중 하나이다. 전체 연결 그래프 중에서 모든 정점을 포함해야하고,

정점들끼리 간선을 통해 서로 연결되면서 사이클은 존재하지 않는 그래프이다.

이러한 신장트리 중에 최소비용을 가진 최소비용신장트리를 구해야한다.

크루스칼 알고리즘을 사용하기 이전에 우선 Union-Find기법이 무엇인지 알아보자.

Union-Find ?

Union-Find란 '공통 원소가 없는 상호배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장한 자료구조' 이다.

Union-Find 구현은 주로 트리구조를 이용한다.

다음은 Union-Find의 대표적인 3가지 기능이다.

• 초기화 : N개의 원소가 모두 루트 노드가 되고, 자기 자신을 가르키는 포인터를 가지도록 설정한다.
• Union : a, b 두 원소가 주어진다면 각자 원소의 루트를 찾은 뒤, 다르다면 두 트리를 합친다.
• Find : 각 노드에 저장된 포인터를 따라 트리의 루트 노드를 찾는다.

》》 초기화

for(int i = 0; i <= n; i++){

parent[i] = i; // 각 노드가 모두 루트 노드가 되도록 초기화

}

》》 Find

int findRoot(int x){

if(x == parent[x]) return x; // 루트 노드라면 반환

return findRoot(parent[x]) // 부모 노드를 찾아 올라간다.

}

》》 Union

void merge(int x, int y){

x = findRoot(x);

y = findRoot(y);

if(x == y) return; // x와 y가 이미 같은 트리에 존재한다면 합치지 않는다.

parent[x] = y;

}

하지만 위와 같이 구현을 할 시, 최악의 경우 다음과 같은 완전히 비대칭 트리가 되어버릴 수 있다는 단점이 있다.

이 문제를 해결하기 위해 level이라는 변수를 이용한다.

》》 초기화

for(int i = 0; i <= n; i++){

parent[i] = i;

level[i] = 1; // 초기 트리는 모두 1로 초기화

}

》》 Find

int findRoot(int x){

if(x == parent[x]) return x;

return findRoot(parent[x]);

}

》》 Union

void merge(int x, int y){

x = findRoot(x);

y = findRoot(y);

if(x == y) return;

if(level[x] > level[y]) swap(x, y); // 항상 x가 더 작은 트리가 되도록 설정

parent[x] = y;

if(level[x] == level[y]) ++level[x]; // 깊이가 같을 경우 x의 level을 늘려준다.

}

이제 Union-Find 자료구조를 이용해 크루스칼 알고리즘을 구현해보자

크루스칼 알고리즘의 기본적인 아이디어는 다음과 같다.

1. 가장 작은 가중치부터 추가하기 위해 가중치에 대한 오름차순으로 정렬한다.
2. 가장 가중치가 작은 것부터 추가하며 사이클이 생기면 가장 높은 가중치 부터 뺀다.
3. 1번의 결과로 가장 마지막에 넣은 간선이 가장 높은 가중치를 가지므로 애초에 추가하지 않고 1번의 단계를 건너뛰면 된다.
4. 이 과정에서 빠른 속도로 사이클의 여부를 따져보기 위해 Union-Find를 사용한다.

예시 : 백준 알고리즘 1197번 문제

https://github.com/jobcing/Algorithm/blob/master/src/mst/BOJ_1197.java

※ 참조 :

http://www.leafcats.com/76

http://bowbowbow.tistory.com/26

http://www.crocus.co.kr/683