[알고리즘 공부] 크루스칼 알고리즘 Kruskal's Algorithm

크루스칼 알고리즘이란?

최소 신장 트리 구현에 사용되는 알고리즘으로, 가중치가 있는 그래프의 모든 간선들을 대상으로

1. 최소 비용의 간선으로 구성
2. 사이클을 형성하지 않음

의 조건을 지켜가며 각 단계마다 최선의 해를 선택하기에 그리디 알고리즘에 기원을 둔다.

 

크루스칼 알고리즘의 시퀀스

1. 그래프의 간선들을 가중치 기준으로 오름차순 정렬한다.
2. 정렬된 간선들 중 가중치가 작은 순서대로 사이클을 형성하지 않는 한 선택한다.
3. 선택된 간선으로 MST를 구현한다.
4. MST 집합의 원소의 개수가 V-1개가 될때까지 위 단계를 반복한다.

이때, 주의해야 할 점은 사이클을 형성하지 않게 정렬된 간선들을 선택한다는 것이다. 따라서 사이클을 형성하는지 안하는지에 대한 판가름을 해줄 수 있는 메소드를 같이 구현해야 한다.

크루스칼 알고리즘으로 MST 구하기

 

크루스칼 알고리즘 vs 프림 알고리즘

크루스칼 알고리즘 : Kruskal's Algorithm	프림 알고리즘 : Prim's Algorithm
그래프의 최소 가중치 간선들을 정렬된 순서로 추가하여 MST 구성	그래프의 아무 정점부터 시작하여 MST 구성
통상적으로 O(E logV)의 시간복잡도	통상적으로 O(E + V logV)의 시간복잡도
주로 간선의 수가 적은 희소그래프_Sparse Graph에 유리	주로 간선의 수가 많은 밀집그래프_Dense Graph에 유리