크루스칼 알고리즘 (Kruskal’s Algorithm)
크루스칼 알고리즘이란
크루스칼 알고리즘은 간선 중심의 탐욕 알고리즘으로 최소 신장 트리를 구하는 방법으로, 간선을 가중치 순으로 정렬한 후, 사이클을 만들지 않는 간선을 하나씩 선택하여 최소 신장 트리(MST)를 만드는 알고리즘이다.
알고리즘 시각화
동작 예시
아래와 같은 그래프가 주어졌을 때 크루스칼 알고리즘의 동작 과정을 살펴보자.
(A)
2/ \3
(B) (C)
1\ /4
(D)1단계: 간선 정렬
모든 간선을 가중치 오름차순으로 정렬한다.
정렬된 간선: B-D(1), A-B(2), A-C(3), C-D(4)
2단계: 간선 선택
가중치가 작은 간선부터 사이클 여부를 확인하며 선택한다.
- B-D(1) 선택 → 사이클 없음 → MST에 추가 ✓
- A-B(2) 선택 → 사이클 없음 → MST에 추가 ✓
- A-C(3) 선택 → 사이클 없음 → MST에 추가 ✓
- C-D(4) 선택 → 사이클 발생 (C와 D가 이미 연결됨) → 건너뛰기 ✗
3단계: 완성
- 선택된 간선: 3개 (V-1 = 4-1 = 3)
- 최소 가중치 합: 1 + 2 + 3 = 6
복잡도
| 구분 | 복잡도 | 설명 |
|---|---|---|
| 시간 복잡도 | O(E log E) | - 간선 정렬: O(E log E) - Union-Find 연산: O(E × α(V)) |
| 공간 복잡도 | O(V + E) | - 간선 리스트: O(E) - Union-Find 배열: O(V) |
장단점
| 장점 | 단점 |
|---|---|
| 간단한 구현 - 알고리즘이 직관적 - 코드가 비교적 짧음 | 정렬 필요 - 간선 정렬에 O(E log E) 소요 - 간선이 많으면 비효율적 |
| 희소 그래프에 유리 - 간선이 적을 때 효율적 - E가 작으면 정렬 비용 감소 | Union-Find 구현 필요 - 별도의 자료구조 구현 필요 - 최적화 없이는 비효율적 |
주의사항
- 그래프가 연결되어 있어야 MST 존재
- Union-Find 최적화 필수 (경로 압축, 랭크)
- 간선 가중치가 같으면 MST가 여러 개 가능
- 0-indexed vs 1-indexed 주의
- 간선이 많으면 프림 알고리즘 고려
Last updated on