국가에서 대한민국 100개의 주요 도시를 모두 연결하는 초고속 광랜 인터넷 케이블 공사를 진행한다고 상상해 보십시오. 각 도시를 잇는 케이블의 설치 비용은 모두 다릅니다. 국가의 예산은 한정되어 있으므로, 모든 도시가 통신망으로 끊김 없이 연결되면서도 전체 케이블 설치 비용의 합은 최소가 되도록 설계해야 합니다. 불필요하게 빙글빙글 도는 순환 도로(Cycle)를 만들어서 비용을 낭비해서도 안 됩니다. 이러한 현실 세계의 인프라 구축 문제를 컴퓨터 공학의 그래프 이론으로 완벽하게 해결해 주는 알고리즘이 바로 최소 신장 트리(Minimum Spanning Tree, 이하 MST)를 구하는 크루스칼(Kruskal)과 프림(Prim) 알고리즘입니다. 목적은 같지만 접근 방식이 정반대인 두 천재적인 알고리즘을 비교해 보겠습니다.
1. 최소 신장 트리(MST)의 개념
크루스칼과 프림을 이해하기 전에, 먼저 이들이 찾고자 하는 궁극적인 목표인 MST가 무엇인지 알아야 합니다.
- 신장 트리 (Spanning Tree): 주어진 그래프 내의 모든 정점(Node)을 포함하면서, 간선들로 서로 모두 연결되어 있으되 사이클(순환)이 절대 존재하지 않는 부분 그래프를 말합니다. 노드가 $N$개라면 간선은 반드시 $N-1$개만 존재해야 합니다.
- 최소 신장 트리 (MST): 여러 개의 신장 트리들 중에서, 사용된 간선들의 가중치(비용) 총합이 가장 적은 트리를 의미합니다.
2. 크루스칼(Kruskal) 알고리즘: 간선을 중심으로 한 탐욕적 선택
조셉 크루스칼(Joseph Kruskal)이 고안한 이 알고리즘은 정점(도시)의 위치는 신경 쓰지 않고, 오직 '가장 비용이 싼 간선(케이블)'부터 무조건 줍고 보는 철저한 탐욕(Greedy) 알고리즘입니다.
2-1. 동작 원리와 유니온 파인드(Union-Find)
- 정렬: 그래프 내의 모든 간선을 가중치(비용)가 적은 순서대로 오름차순 정렬합니다.
- 선택: 가장 비용이 적은 간선부터 순서대로 하나씩 뽑습니다.
- 사이클 검증 (핵심): 뽑은 간선이 두 정점을 연결할 때, 혹시라도 사이클(Cycle)이 형성되는지 검사합니다. 만약 사이클이 만들어진다면 이 간선은 버리고, 다음으로 싼 간선을 고릅니다.
- 종료: 이렇게 선택된 간선의 개수가 $V-1$개(정점 개수 - 1)가 되면 완벽한 MST가 완성되므로 알고리즘을 종료합니다.
여기서 사이클이 발생하는지 확인하는 기술이 매우 중요한데, 이때 노드들이 같은 집합(네트워크)에 속해 있는지 빠르게 파악하는 '유니온-파인드(Union-Find, 분리 집합)' 자료구조가 필수적으로 결합되어 사용됩니다. 전체 간선을 정렬하는 시간에 의해 크루스칼의 성능이 결정되므로, 시간 복잡도는 $O(E \log E)$가 됩니다.
3. 프림(Prim) 알고리즘: 정점을 중심으로 한 영토 확장
로버트 프림(Robert Prim)이 고안한 알고리즘은 크루스칼과는 완전히 다른 시각으로 접근합니다. 임의의 시작 정점 하나를 콕 집은 뒤, 주변의 정점들을 하나씩 흡수하며 영토를 넓혀나가는 방식입니다. 앞서 배운 다익스트라 알고리즘과 동작 메커니즘이 매우 흡사합니다.
3-1. 동작 원리와 우선순위 큐(Priority Queue)
- 시작점 지정: 아무 노드나 하나 골라서 MST의 첫 영토로 편입시킵니다.
- 간선 큐 삽입: 현재까지 MST 영토에 편입된 모든 노드들과 인접해 있는 외부 간선들을 전부 우선순위 큐(Min-Heap)에 집어넣습니다.
- 최단 간선 확장: 우선순위 큐에서 가장 비용이 적은 간선을 뽑아냅니다(Pop). 만약 이 간선과 연결된 반대쪽 노드가 이미 MST 영토에 속해있다면 무시(사이클 방지)하고, 아직 편입되지 않은 새로운 노드라면 영토에 추가합니다.
- 종료: 모든 노드가 영토에 편입될 때까지 2번과 3번 과정을 반복합니다.
프림 알고리즘은 힙(우선순위 큐)을 활용해 인접한 간선들 중 최솟값을 빠르게 뽑아내므로, 시간 복잡도는 $O(E \log V)$ 수준을 보여줍니다.
4. 크루스칼 vs 프림: 실전 선택 가이드
두 알고리즘은 모두 100% 완벽한 MST를 찾아주지만, 그래프의 밀집도(Density)에 따라 압도적으로 유리한 전장이 다릅니다.
- 간선이 듬성듬성한 희소 그래프 (Sparse Graph): 도시(정점)는 많은데 놓을 수 있는 도로(간선)의 가짓수는 적은 경우입니다. 이때는 간선을 정렬해 놓고 뽑는 크루스칼(Kruskal) 알고리즘이 훨씬 빠르고 유리합니다.
- 간선이 빽빽하게 얽힌 밀집 그래프 (Dense Graph): 도시들이 그물망처럼 서로 전부 연결되어 간선의 개수가 엄청나게 많은 경우입니다. 간선 정렬에 너무 오랜 시간이 걸리므로, 노드를 중심으로 뻗어 나가는 프림(Prim) 알고리즘을 선택하는 것이 연산 속도 측면에서 월등히 탁월한 선택입니다.
1. 최소 신장 트리(MST)는 그래프 내의 모든 정점을 사이클 없이 연결하는 최소 비용의 네트워크 구조입니다.
2. 크루스칼(Kruskal)은 전체 간선을 비용 순으로 정렬 후 저렴한 것부터 줍는 탐욕법으로, 유니온-파인드(Union-Find)를 사용하여 희소 그래프에 적합합니다.
3. 프림(Prim)은 시작 정점에서부터 인접한 가장 싼 간선을 골라 영토를 확장하는 기법으로, 우선순위 큐를 사용하여 밀집 그래프에서 탁월한 성능을 냅니다.