CS학습2026년 8월 26일

Prim: 정점 기준으로 확장하는 최소 신장 트리 알고리즘

Prim 알고리즘은 하나의 시작 정점에서 출발해 이미 선택된 정점 집합과 연결된 간선 중 가장 가중치가 작은 간선을 반복적으로 선택하여 최소 신장 트리(MST)를 구성하는 그리디(Greedy) 알고리즘이다. 우선순위 큐(Priority Queue)를 사용하면 O(E log V)에 동작하며, 밀집 그래프(dense graph)에서 Kruskal보다 유리한 경

송민성5분 읽기

1. 개념

Prim 알고리즘은 가중치가 있는 무방향 연결 그래프(weighted undirected connected graph)에서 최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 알고리즘이다. MST는 그래프의 모든 정점을 포함하면서 사이클이 없고, 간선 가중치의 합이 최소인 부분 그래프를 말한다.

Kruskal 알고리즘이 간선(edge) 중심으로 전체를 정렬해서 선택하는 방식이라면, Prim은 정점(vertex) 중심으로 트리를 점점 넓혀가는 방식이다. 시작 정점 하나에서 출발해서, 현재 트리에 속한 정점과 아직 속하지 않은 정점을 잇는 간선 중 가장 가중치가 작은 것을 매번 선택한다.

2. 왜 사용하는가

네트워크 설계, 클러스터링, 회로 설계처럼 "모든 노드를 최소 비용으로 연결"해야 하는 문제는 실무에서 자주 등장한다. 예를 들어 여러 도시를 도로로 연결하되 총 건설 비용을 최소화하거나, 여러 서버를 네트워크 케이블로 연결할 때 총 케이블 길이를 최소화하는 문제가 대표적이다.

Prim은 특히 간선 수가 정점 수에 비해 많은 밀집 그래프(dense graph)에서 유리하다. Kruskal은 전체 간선을 정렬해야 해서 간선이 많을수록 부담이 크지만, Prim은 우선순위 큐를 통해 필요한 간선만 다루기 때문이다.

3. 동작 원리

임의의 시작 정점을 선택하고 MST 집합에 포함시킨다.
MST 집합에 속한 정점과 인접한 간선들을 우선순위 큐에 넣는다.
우선순위 큐에서 가중치가 가장 작은 간선을 꺼낸다. 이때 간선의 반대쪽 정점이 이미 MST에 포함되어 있으면 버리고(사이클 방지), 아니면 MST에 추가한다.
새로 추가된 정점과 인접한 간선들을 다시 큐에 넣는다.
모든 정점이 MST에 포함될 때까지 2~4를 반복한다.

핵심은 "현재까지 만든 트리와 바깥을 잇는 간선 중 최솟값"을 매번 그리디하게 선택한다는 점이다. 이 그리디 선택이 항상 전역 최적(global optimum)이 되는 이유는 컷 속성(Cut Property)으로 증명된다. 어떤 정점 집합과 그 나머지를 나누는 컷(cut)에서 가장 가벼운 간선은 반드시 어떤 MST에 포함된다는 성질이다.

4. 코드 예제

python

import heapq

def prim(graph: dict[int, list[tuple[int, int]]], start: int) -> tuple[list[tuple[int, int, int]], int]:
    """
    graph: 인접 리스트, {정점: [(인접정점, 가중치), ...]}
    start: 시작 정점
    반환: (MST에 포함된 간선 리스트, 총 가중치)
    """
    visited = set([start])
    edges = [(weight, start, to) for to, weight in graph[start]]
    heapq.heapify(edges)

    mst_edges = []
    total_weight = 0

    while edges and len(visited) < len(graph):
        weight, frm, to = heapq.heappop(edges)

        if to in visited:
            continue  # 사이클을 만드는 간선은 버린다

        visited.add(to)
        mst_edges.append((frm, to, weight))
        total_weight += weight

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

    return mst_edges, total_weight


# 그래프 예시: 정점 0~4, 무방향 간선
graph = {
    0: [(1, 2), (3, 6)],
    1: [(0, 2), (2, 3), (3, 8), (4, 5)],
    2: [(1, 3), (4, 7)],
    3: [(0, 6), (1, 8), (4, 9)],
    4: [(1, 5), (2, 7), (3, 9)],
}

mst_edges, total_weight = prim(graph, start=0)
print("MST 간선:", mst_edges)
print("총 가중치:", total_weight)
# MST 간선: [(0, 1, 2), (1, 2, 3), (1, 4, 5), (0, 3, 6)]
# 총 가중치: 16

5. 시간 복잡도 또는 성능 특성

구현 방식에 따라 시간 복잡도가 달라진다.

| 구현 방식 | 시간 복잡도 | 비고 | |---|---|---| | 인접 행렬 + 선형 탐색 | O(V²) | 밀집 그래프에서 유리 | | 인접 리스트 + 이진 힙(우선순위 큐) | O(E log V) | 일반적으로 가장 많이 사용 | | 인접 리스트 + 피보나치 힙 | O(E + V log V) | 이론적으로 최적, 실무에서는 상수 계수 때문에 잘 안 씀 |

공간 복잡도는 인접 리스트 기준 O(V + E)이다.

Kruskal의 시간 복잡도는 O(E log E)로 간선 정렬이 지배적이다. 정점 수(V)에 비해 간선 수(E)가 V²에 가까운 밀집 그래프에서는 Prim(O(E log V))이 유리하고, 간선이 적은 희소 그래프(sparse graph)에서는 Kruskal이 더 단순하고 효율적인 경우가 많다.

6. 실무 사용 사례

네트워크 설계: 여러 지점을 최소 비용의 케이블/회선으로 연결하는 인프라 설계
클러스터링: 계층적 클러스터링(hierarchical clustering)에서 MST를 활용해 데이터 포인트 간 거리 기반 그룹화
이미지 분할(image segmentation): 픽셀을 그래프의 정점으로 보고 MST 기반으로 영역을 나누는 컴퓨터 비전 기법
회로 설계: PCB에서 배선 길이를 최소화하는 라우팅 문제의 근사 해법
근사 알고리즘의 하위 루틴: 외판원 문제(TSP)의 근사 알고리즘 중 하나가 MST를 기반으로 한다

7. 주의할 점

Prim은 연결 그래프(connected graph)를 전제로 한다. 그래프가 연결되어 있지 않으면 시작 정점이 속한 연결 요소(connected component)의 MST만 구해지고 나머지 정점은 무시된다. 이 경우 최소 신장 숲(Minimum Spanning Forest)을 구하려면 각 연결 요소마다 별도로 실행해야 한다.
무방향 그래프 전용 알고리즘이다. 방향 그래프(directed graph)의 최소 비용 스패닝 구조가 필요하면 최소 신장 아보레센스(minimum spanning arborescence) 문제로 넘어가야 하며, 이때는 Chu-Liu/Edmonds 알고리즘을 사용한다.
가중치가 음수여도 알고리즘 자체는 정상 동작한다(다익스트라와 달리 음수 가중치 문제가 없다). MST는 최단 경로 문제가 아니라 전체 간선 합의 최소화 문제이기 때문이다.
우선순위 큐에 중복 정점이 여러 번 들어갈 수 있으므로, visited 체크를 큐에서 꺼낼 때(pop 시점) 반드시 해야 한다. 삽입 시점에만 체크하면 이미 큐에 들어간 오래된(stale) 항목 때문에 오류가 생길 수 있다.

8. 핵심 정리

Prim은 시작 정점에서부터 트리를 점진적으로 확장하며, 매 단계마다 현재 트리와 바깥을 잇는 최소 가중치 간선을 그리디하게 선택해 MST를 구성하는 알고리즘이다. 우선순위 큐를 활용하면 O(E log V)에 동작하며, 간선이 많은 밀집 그래프에서 Kruskal보다 유리한 선택지가 된다. 연결 그래프와 무방향 그래프라는 전제 조건, 그리고 우선순위 큐에서 pop 시점에 방문 여부를 확인해야 한다는 구현상의 디테일을 기억해 둘 필요가 있다.