Algorithm Guidecomplexity: O(E log V)

프림 (Prim MST)

한 노드에서 시작해 트리에 연결된 가장 싼 간선을 하나씩 더해 가며 최소 신장 트리를 키웁니다. 우선순위 큐로 후보 간선을 관리하며, 크루스칼과 다른 순서로 자라지만 동일한 MST에 도달합니다.

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

Prim MST

Prim 시작. 시작 노드 A의 key를 0, 나머지는 ∞로 둡니다. 트리를 A부터 한 노드씩 키워 갑니다.

Logic Node1 / 7

Live Python

1import heapq

2def prim(graph, start):

# visited = {A}

3 visited = {start}

4 pq = [(w, start, v) for v, w in graph[start]]

5 heapq.heapify(pq)

6 mst, total = [], 0

7 while pq:

8 w, u, v = heapq.heappop(pq)

9 if v in visited:

10 continue

11 visited.add(v)

12 mst.append((u, v)); total += w

13 for nxt, w2 in graph[v]:

14 if nxt not in visited:

15 heapq.heappush(pq, (w2, v, nxt))

16 return mst, total

02 쉽게 이해하기

For Everyone

🔑비유

한 마을에서 시작해 가장 가까운 마을을 하나씩 이어 붙이는 것.

💡쉽게 말하면

트리에 연결된 가장 싼 간선을 하나씩 더하며 최소 신장 트리를 키웁니다.

크루스칼과 다른 순서지만 같은 결과예요.

📍어디에 쓰나

–최소 비용 연결망
–밀집 그래프의 MST

03 파이썬 구현 코드

프림 (Prim MST)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

import heapq

def prim(graph, start):
    visited = {start}
    pq = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(pq)
    mst, total = [], 0
    while pq:
        w, u, v = heapq.heappop(pq)
        if v in visited:
            continue
        visited.add(v)
        mst.append((u, v))
        total += w
        for nxt, w2 in graph[v]:
            if nxt not in visited:
                heapq.heappush(pq, (w2, v, nxt))
    return mst, total