프림 알고리즘: 정점 중심 MST 구축과 성능 최적화

최소 신장 트리(MST)를 구하는 두 번째 거대한 축인 프림(Prim) 알고리즘은 크루스칼과는 전혀 다른 관점에서 문제에 접근합니다. 크루스칼이 간선을 하나씩 주워 모으는 방식이라면, 프림은 하나의 씨앗 정점에서 시작해 주변으로 세력을 확장하며 트리를 키워나가는 방식입니다. 본 포스팅에서는 프림 알고리즘의 동작 매커니즘과 우선순위 큐를 활용한 최적화 기법, 그리고 크루스칼과의 결정적 차이점을 2,500자 분량의 심도 있는 기술적 분석으로 다루어 보겠습니다.

1. 프림 알고리즘의 핵심 로직과 확장 원리

프림 알고리즘의 기본 아이디어는 매우 단순하면서도 강력합니다. 임의의 정점을 하나 선택해 트리의 시작점으로 삼습니다. 이후 현재까지 형성된 트리에 속한 노드들과 연결된 모든 간선 중에서, 트리에 속하지 않은 새로운 노드와 연결된 가장 저렴한 간선을 선택하여 트리를 확장합니다. 이 과정을 모든 정점이 포함될 때까지 반복하는 것입니다. 이는 다익스트라 최단 경로 알고리즘과 매우 유사한 구조를 가지고 있습니다.

1-1. 정점 중심 탐색의 장점

간선 중심의 크루스칼은 사이클 여부를 매번 확인해야 하지만, 프림은 '이미 트리에 포함된 노드'와 '아직 포함되지 않은 노드'를 구분하여 탐색하므로 구조적으로 사이클이 발생할 위험을 사전에 차단합니다. 이러한 특성 덕분에 프림 알고리즘은 간선이 빽빽하게 들어찬 밀집 그래프(Dense Graph)에서 크루스칼보다 우수한 효율성을 보여줍니다.

2. 우선순위 큐(Priority Queue)를 이용한 성능 혁신

단순히 인접한 간선을 선형 탐색으로 찾으면 매 단계마다 $O(V)$의 시간이 걸려 전체 복잡도가 $O(V^2)$이 됩니다. 하지만 최소 힙(Min Heap)을 기반으로 한 우선순위 큐를 도입하면, 현재 연결 가능한 간선 중 최솟값을 찾는 과정을 $O(\log E)$로 줄일 수 있습니다. 이는 정점과 간선의 수가 수만 개를 넘어서는 대규모 인프라 설계 데이터에서 연산 시간을 획기적으로 단축해 줍니다.

2-1. 단계별 알고리즘 프로세스

임의의 시작 정점을 방문 처리하고, 해당 정점과 연결된 모든 간선을 우선순위 큐에 삽입합니다.
큐가 빌 때까지 다음 과정을 반복합니다.
- 큐에서 가장 가중치가 낮은 간선을 꺼냅니다.
- 해당 간선이 가리키는 대상 노드가 이미 방문된 상태라면 무시합니다.
- 아직 방문 전이라면 트리에 포함시키고, 그 노드와 연결된 새로운 간선들을 다시 큐에 넣습니다.

3. 크루스칼 vs 프림: 데이터 특성에 따른 현명한 선택

두 알고리즘은 목적이 같지만 성능이 극대화되는 지점이 다릅니다. 크루스칼의 복잡도는 $O(E \log E)$이며, 프림의 복잡도는 우선순위 큐 사용 시 $O(E \log V)$입니다. 언뜻 비슷해 보이지만, 간선의 수가 $V^2$에 육박하는 밀집 그래프에서는 정렬 비용이 큰 크루스칼보다 프림이 훨씬 유리합니다. 반대로 간선이 매우 적은 트리 형태에 가까운 그래프라면 크루스칼이 더 직관적이고 빠를 수 있습니다.

실무 적용: 지능형 전력망 및 네트워크 라우팅

프림 알고리즘은 전력망에서 변전소를 효율적으로 배치하거나, 가상 사설망(VPN)의 멀티캐스트 트리 구축 등에서 핵심적으로 사용됩니다. 특히 노드(지점) 간의 연결 가능성이 거의 무한에 가까운 실제 물리적 지형 데이터에서 프림의 정점 중심 확장 방식은 매우 안정적인 결과물을 제공합니다.


# 파이썬 heapq 라이브러리를 활용한 프림 알고리즘 구현
import heapq

def prim(start_node, n, adj):
    visited = [False] * (n + 1)
    pq = [(0, start_node)] # (가중치, 노드)
    total_weight = 0
    
    while pq:
        weight, u = heapq.heappop(pq)
        if visited[u]:
            continue
        
        visited[u] = True
        total_weight += weight
        
        for v, w in adj[u]:
            if not visited[v]:
                heapq.heappush(pq, (w, v))
    return total_weight

[프림 알고리즘 핵심 요약]
1. 정점 중심: 하나의 시작점에서 주변의 최소 가중치 간선을 선택하며 세력을 넓히는 방식입니다.
2. 성능 최적화: 우선순위 큐(Heap)를 사용하여 최솟값 추출 시간을 $O(\log E)$로 단축합니다.
3. 적용 환경: 정점에 비해 간선의 수가 압도적으로 많은 밀집 그래프 환경에서 권장됩니다.

kguidebook0001 님의 블로그