여러 도시를 연결하는 도로망을 구축하거나 통신 선로를 설계할 때, 가장 중요한 목표는 '모든 지점을 연결하되 총비용을 최소화'하는 것입니다. 이를 그래프 이론에서는 최소 신장 트리(Minimum Spanning Tree, MST)라고 부릅니다. MST를 구하는 가장 대표적인 두 알고리즘이 바로 크루스칼(Kruskal)과 프림(Prim)입니다. 두 알고리즘은 모두 '그리디(Greedy)' 방식을 취하지만, 접근 방식과 효율적인 데이터 구조가 완전히 다릅니다.
1. 크루스칼(Kruskal) 알고리즘: 간선 중심의 접근
크루스칼 알고리즘은 그래프의 모든 간선(Edge)을 가중치 기준으로 오름차순 정렬한 뒤, 가중치가 낮은 간선부터 하나씩 트리에 포함시키는 방식입니다.
1-1. 핵심 원리와 사이클 방지
단순히 짧은 간선만 선택하다 보면 사이클(Cycle)이 발생할 수 있습니다. 이를 방지하기 위해 Union-Find(서로소 집합) 자료구조를 필수적으로 사용합니다. 선택하려는 간선의 두 정점이 이미 같은 집합에 속해 있다면 사이클이 생기므로 건너뛰고, 다른 집합이라면 합치는(Union) 과정을 반복합니다.
- 시간 복잡도: 간선 정렬에 소요되는 O(E log E)가 지배적입니다.
- 장점: 간선의 개수가 적은 희소 그래프(Sparse Graph)에서 유리합니다.
2. 프림(Prim) 알고리즘: 정점 중심의 접근
프림 알고리즘은 하나의 시작 정점에서 시작하여, 현재 트리에 포함된 정점들과 연결된 간선 중 가장 가중치가 작은 간선을 선택하며 트리를 확장해 나가는 방식입니다.
2-1. 우선순위 큐를 활용한 최적화
매 단계마다 최소 가중치 간선을 찾아야 하므로 우선순위 큐(Priority Queue)나 힙(Heap) 자료구조를 사용합니다. 현재 방문한 정점 집합에서 갈 수 있는 모든 경로를 큐에 넣고, 가장 짧은 것을 꺼내 방문하지 않은 정점과 연결하는 방식입니다.
- 시간 복잡도: 우선순위 큐 구현 시 O(E log V)를 가집니다.
- 장점: 정점에 비해 간선이 매우 많은 밀집 그래프(Dense Graph)에서 성능이 뛰어납니다.
3. 어떤 알고리즘을 선택해야 할까?
그래프의 형태에 따라 선택 기준이 달라집니다. 노드의 개수가 V, 간선의 개수가 E일 때,
| 특징 | 크루스칼(Kruskal) | 프림(Prim) |
|---|---|---|
| 주요 대상 | 간선(Edge) | 정점(Vertex) |
| 자료구조 | Union-Find, 정렬 | 우선순위 큐(Heap) |
| 그래프 형태 | 간선이 적은 그래프(희소) | 간선이 많은 그래프(밀집) |
1. 공통점: 두 알고리즘 모두 그리디 전략을 사용하여 전역 최적해인 MST를 찾아냅니다.
2. 차이점: 크루스칼은 간선을 정렬하여 사이클을 검사하고, 프림은 정점을 확장하며 최소 경로를 찾습니다.
3. 실무 팁: 그래프의 밀집도에 따라 간선이 적으면 크루스칼, 많으면 프림을 선택하는 것이 표준입니다.