Prim 알고리즘으로 최소 신장 트리 구성하기

현재 트리에서 가장 싼 연결을 하나씩 고른다

Prim 알고리즘은 연결된 가중치 그래프에서 최소 신장 트리(MST)를 만드는 대표적인 방법이다. 임의의 정점에서 출발해, 이미 선택한 정점 집합과 바깥 정점을 잇는 간선 가운데 가중치가 가장 작은 것을 계속 추가한다.

새 간선을 고를 때 트리에 이미 속한 두 정점을 다시 연결하는 간선은 대상에서 제외한다. 이 조건으로 사이클 없이 모든 정점을 포함하는 트리를 구성한다.

이 알고리즘은 1930년 체코의 수학자 Vojtěch Jarník가 처음 발견했고, 1957년 Robert C. Prim이 재발견하면서 널리 알려졌다.

선택 집합을 확장하는 방식

처리는 시작 정점 선택에서 시작한다. 이후 현재 선택된 정점들과 미선택 정점 사이의 간선을 살피고, 그중 최소 가중치 간선을 골라 새 정점을 트리에 편입한다. 모든 정점이 트리에 들어올 때까지 이 과정을 반복한다.

그래프가 비연결이면 한 성분의 처리가 끝난 뒤 아직 선택되지 않은 정점에서 다시 시작할 수 있다. 이렇게 연결 성분마다 Prim을 수행하면 하나의 MST 대신 최소 신장 숲(MSF)을 만든다.

다익스트라 알고리즘과의 형태상 유사성 때문에 구현을 함께 떠올리기 쉽다. 두 알고리즘 모두 우선순위 큐를 쓸 수 있지만, 큐의 키가 뜻하는 바는 다르다. Prim은 후보 간선의 실제 가중치를 기준으로 최소 신장 트리를 만들고, 다익스트라는 시작점부터 누적된 거리를 기준으로 최단 경로를 찾는다.

우선순위 큐를 이용한 의사 코드

function Prim(G, start):
    MST = empty set
    visited[1...n] = false
    key[1...n] = infinity
    key[start] = 0
    parent[start] = NULL

    priority_queue Q = all vertices with keys

    while Q is not empty:
        u = extract_min(Q)
        visited[u] = true

        for each neighbor v of u:
            if visited[v] == false and weight(u,v) < key[v]:
                parent[v] = u
                key[v] = weight(u,v)
                decrease_key(Q, v, key[v])

    for i = 1 to n:
        if parent[i] != NULL:
            MST.add(edge(i, parent[i]))

    return MST

우선순위 큐의 구현에 따라 시간 복잡도와 적합한 그래프가 달라진다.

구현 방식	시간 복잡도	적합한 경우
단순 배열	O(V²)	밀집 그래프
바이너리 힙	O(E log V)	희소 그래프
피보나치 힙	O(E + V log V)	희소 그래프

단순 배열은 밀집 그래프에서 더 효율적일 수 있다. 간선 수가 적은 희소 그래프에서는 힙 기반 구현이 유리하다.

예시 그래프에서의 간선 선택

⤢✕

정점 A에서 시작하면 A-B(2)를 먼저 선택한다. 이어 B-D(1)를 추가하고, 현재 MST(A-B-D)와 연결되는 간선 가운데 B-C(3)를 고른다. 마지막으로 MST(A-B-D-C)에서 D-E(6)를 선택하면 모든 정점이 포함된다.

최종 MST 간선은 {A-B(2), B-D(1), B-C(3), D-E(6)}이며, 총 가중치는 12다.

네트워크와 인프라 연결 비용을 다룰 때

Prim 알고리즘은 모든 지점을 연결하되 연결 비용을 줄여야 하는 문제에 적용할 수 있다. 통신망에서는 케이블 최소화와 라우터 간 최소 비용 연결 설계에, 전력 그리드에서는 전력선 구축 비용과 전력 분배 네트워크 구성에 활용된다. 임의 연결 대비 간선 비용 합 10~40% 절감 가능하며, 이 범위는 가중치 분포와 제약에 따라 달라진다.

운송 시스템에서는 도로 건설 비용과 물류 네트워크 최적화에 연결된다. 가스·수도 공급망을 설계하는 파이프라인 문제에서도 모든 지점을 최소 비용으로 잇는 기준이 된다. 계층적 클러스터링에서는 데이터 포인트 사이의 최소 거리 연결을 구성하는 기반으로 사용할 수 있다.

Kruskal과 다른 간선 선택 기준

특성	Prim	Kruskal
접근 방식	정점 기반	간선 기반
시작	단일 정점에서 시작	모든 정점이 독립적
간선 선택	현재 트리와 연결된 최소 가중치 간선	전체 그래프에서 최소 가중치 간선
사이클 처리	이미 트리에 포함된 정점 무시	Union-Find 구조로 사이클 감지
적합한 그래프	밀집 그래프	희소 그래프

Prim은 하나의 정점에서 트리를 점진적으로 넓힌다. 반면 Kruskal은 그래프 전체의 간선을 가중치 순서로 검토하고 Union-Find 구조로 사이클을 감지한다. 그래프의 밀도와 사용하는 자료구조를 함께 고려해 선택할 수 있다.

자료구조 선택과 대규모 그래프 처리

바이너리 힙은 구현이 간단하면서도 적절한 성능을 제공한다. 피보나치 힙은 이론적 성능이 우수하지만 구현이 복잡하며, 배열은 밀집 그래프에서 효율적이다.

그래프 표현도 밀도에 맞춰야 한다. 인접 행렬은 밀집 그래프에, 인접 리스트는 희소 그래프에 적합하다. 동일한 가중치의 간선이 여러 개라면 정점 ID 순서 같은 일관된 타이브레이커를 정해 두어 결과를 재현하고 검증할 수 있어야 한다. 그래프 표현과 동률 처리 정책은 선택 순서와 결과에 영향을 준다.

대규모 그래프에서는 메모리 사용량과 필요한 자료구조의 최적화를 함께 검토해야 한다. 규모가 큰 경우 부분 그래프에 대한 병렬 처리 전략도 고려 대상이 된다.

Python 구현

import heapq

def prim(graph, start):
    mst = []
    visited = set([start])
    edges = [(cost, start, to) for to, cost in graph[start].items()]
    heapq.heapify(edges)

    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, cost))

            for next_to, next_cost in graph[to].items():
                if next_to not in visited:
                    heapq.heappush(edges, (next_cost, to, next_to))

    return mst

# 그래프 예시
graph = {
    'A': {'B': 2, 'C': 4},
    'B': {'A': 2, 'C': 3, 'D': 1},
    'C': {'A': 4, 'B': 3, 'D': 5, 'E': 7},
    'D': {'B': 1, 'C': 5, 'E': 6},
    'E': {'C': 7, 'D': 6}
}

result = prim(graph, 'A')
print("최소 신장 트리:", result)
print("총 가중치:", sum(cost for _, _, cost in result))

# prim_mst.py
# Usage: python3 prim_mst.py
from heapq import heappush, heappop

def prim_mst(adj, start=0):
    """
    adj: dict[int, list[tuple[int, float]]]  # u: [(v, w), ...]
    start: 시작 정점
    반환: (edges, total_weight)  # edges: list[(u, v, w)]
    비연결 그래프인 경우 최소 신장 숲(MSF) 반환
    """
    visited = set()
    result = []
    total = 0.0

    def run_from(s):
        nonlocal total
        pq = []
        visited.add(s)
        for v, w in adj.get(s, []):
            heappush(pq, (w, s, v))
        while pq:
            w, u, v = heappop(pq)
            if v in visited:
                continue
            visited.add(v)
            result.append((u, v, w))
            total += w
            for nv, nw in adj.get(v, []):
                if nv not in visited:
                    heappush(pq, (nw, v, nv))

    # 성분별 수행
    for s in list(adj.keys()):
        if s not in visited:
            run_from(s)

    return result, total

if __name__ == "__main__":
    # 예시 그래프
    # 0-1:4, 0-2:3, 1-2:1, 1-3:2, 2-3:4, 3-4:2, 2-4:5
    adj = {
        0: [(1, 4), (2, 3)],
        1: [(0, 4), (2, 1), (3, 2)],
        2: [(0, 3), (1, 1), (3, 4), (4, 5)],
        3: [(1, 2), (2, 4), (4, 2)],
        4: [(2, 5), (3, 2)],
    }
    edges, total = prim_mst(adj, start=0)
    print("MST/MSF edges:", edges)
    print("Total weight:", total)

Prim은 정점 기반으로 최소 신장 트리를 확장하므로, 특히 밀집 그래프에서 효율적으로 사용할 수 있다. 우선순위 큐를 활용하면 그래프 특성에 맞춰 성능을 조정할 수 있다.