이 글에서는 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 대표적인 그리디(Greedy) 알고리즘인 프림(Prim) 알고리즘과 크루스칼(Kruskal) 알고리즘의 차이점을 자세히 살펴봅니다.
크루스칼(Kruskal) 알고리즘과 최소 신장 트리(MST)
- 연결된 무방향 그래프가 주어졌을 때, 신장 트리(spanning tree)는 그래프의 모든 정점(vertex)을 연결하는 트리 형태의 부분 그래프입니다.
- 하나의 그래프는 여러 개의 신장 트리를 가질 수 있습니다.
- 가중치가 있는 연결된 무방향 그래프에서 최소 신장 트리(MST)는 다른 모든 신장 트리보다 가중치의 합이 작거나 같은 신장 트리를 의미합니다.
- 신장 트리의 가중치는 트리를 구성하는 모든 간선(edge)의 가중치를 합산하여 계산합니다.
- 크루스칼 알고리즘은 가중치가 가장 작은 간선부터 선택하며 MST를 만들어갑니다.
- 각 노드는 한 번만 순회됩니다.
- 간선 수가 적은 희소 그래프(sparse graph)에서 빠르게 동작합니다.
- 시간 복잡도는 O(E log V)이며, V는 정점의 개수입니다.
- 연결되지 않은 컴포넌트(disconnected component)에도 적용할 수 있습니다.
크루스칼 알고리즘으로 MST를 찾는 단계
- 간선들을 가중치 기준 오름차순으로 정렬합니다.
- 가장 작은 가중치를 가진 간선을 선택합니다.
- 해당 간선이 지금까지 만들어진 신장 트리와 사이클(cycle)을 형성하는지 확인합니다.
- 사이클이 형성되지 않으면 해당 간선을 신장 트리에 포함시킵니다.
- 사이클이 형성된다면 해당 간선은 버립니다.
- 신장 트리가 V-1개의 간선을 가질 때까지 위 과정을 반복합니다.
프림(Prim) 알고리즘과 최소 신장 트리(MST)
- 크루스칼 알고리즘과 마찬가지로 그리디(Greedy) 방식의 알고리즘입니다.
- 빈 신장 트리에서 시작하며, 두 개의 정점 집합을 유지합니다.
- 첫 번째 집합은 이미 MST에 포함된 정점들을, 두 번째 집합은 아직 포함되지 않은 정점들을 담습니다.
- 매 단계마다 두 집합을 연결하는 모든 간선을 검토하고, 그중 가중치가 최소인 간선을 선택합니다.
- 선택한 간선의 반대쪽 끝 정점을 MST가 속한 집합으로 이동시킵니다.
- MST는 그래프의 어떤 정점에서 시작해도 만들 수 있습니다.
- 최소 거리 값을 얻기 위해 하나의 노드를 여러 번 방문할 수 있습니다.
- 시간 복잡도는 O(V²)이며, 피보나치 힙(Fibonacci heap)을 사용하면 O(E + log V)까지 개선할 수 있습니다.
- 간선이 많은 밀집 그래프(dense graph)에서 빠르게 동작합니다.
- 연결 그래프에서만 동작하며, 연결된 컴포넌트를 결과로 제공합니다.
프림 알고리즘으로 MST를 찾는 단계
- MST에 이미 포함된 정점들을 추적하기 위해 mstSet을 생성합니다.
- 입력 그래프의 모든 정점에 키(key) 값을 할당합니다.
- 키 값은 초기에 '무한대(INFINITE)'로 설정합니다.
- 첫 번째 정점에는 키 값 0을 할당하여 가장 먼저 선택되도록 합니다.
- mstSet이 모든 정점을 포함하지 않는 동안 아래 단계를 반복합니다.
- mstSet에 없으면서 키 값이 최소인 정점 'u'를 선택합니다.
- 'u'를 mstSet에 추가합니다.
- 'u'에 인접한 모든 정점의 키 값을 갱신합니다.
- 모든 인접 정점을 순회하며 확인합니다.
- 각 인접 정점 'v'에 대해, 간선 'u-v'의 가중치가 'v'의 기존 키 값보다 작으면 키 값을 'u-v'의 가중치로 갱신합니다.
두 알고리즘 비교 요약
| 구분 | 크루스칼 알고리즘 | 프림 알고리즘 |
|---|---|---|
| 접근 방식 | 간선 중심 | 정점 중심 |
| 시작 조건 | 가중치가 최소인 간선부터 시작 | 그래프의 임의의 정점에서 시작 가능 |
| 시간 복잡도 | O(E log V) | O(V²) (피보나치 힙 사용 시 O(E + log V)) |
| 적합한 그래프 | 희소 그래프 | 밀집 그래프 |
| 연결성 요구 | 비연결 그래프도 처리 가능 | 연결 그래프만 처리 가능 |