크루스칼 알고리즘은, 앞서 배웠던 최소 스패닝 트리(MST)의 구현 알고리즘 중 하나이다.
해당 개념 전, MST의 특징을 다시 짚고 넘어가보자!
1. MST
1.1 특징
- 간선의 가중치의 합이 최소 여야 한다.
- n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
- 사이클이 포함되어서는 안된다.
2. 크루스칼
2.1 알고리즘 절차 요약
1. 간선 정렬
- 그래프의 모든 간선을 비용(가중치)의 오름차순으로 정렬한다.
2. 간선 선택
- 비용이 가장 낮은 간선부터 하나씩 선택하면서,
- 해당 간선이 사이클을 만들지 않는다면 MST(최소 신장 트리)에 추가한다.
(사이클 판단은 Union-Find로 수행)
3. 종료 조건
- 간선이 V-1개(정점 수 - 1) 선택되면 알고리즘을 종료한다.
- 그렇지 않다면 다음 낮은 비용의 간선으로 2번 과정을 반복한다.
2.2 알고리즘 전개
1. 간선 정렬
- 그래프의 모든 간선을 비용(가중치)의 오름차순으로 정렬한다.
2. 간선 선택
- 비용이 가장 낮은 간선부터 하나씩 선택하면서,
- 해당 간선이 사이클을 만들지 않는다면 MST(최소 신장 트리)에 추가한다.
(사이클 판단은 Union-Find로 수행)
3. 종료 조건
- 간선이 V-1개(정점 수 - 1) 선택되면 알고리즘을 종료한다.
- 그렇지 않다면 다음 낮은 비용의 간선으로 2번 과정을 반복한다.
참고
