Algorithm Guidecomplexity: O(E log V)

프림 (Prim MST)

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

01프림 (Prim MST)

알고리즘 작동 원리 탐색

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

A를 트리에 넣고 이웃의 key를 갱신합니다. B는 1, C는 3 — A에서의 간선 가중치입니다.

key가 가장 작은 B(1)를 간선 AB로 트리에 넣습니다. B에서 C의 key가 3→2로 줄고 D는 5가 됩니다.

key가 가장 작은 C(2)를 간선 BC로 넣습니다. C에서 D의 key가 5→4로 줄고 E는 7이 됩니다.

key가 가장 작은 D(4)를 간선 CD로 넣습니다. D에서 E의 key가 7→6으로 줄어듭니다.

마지막으로 E(6)를 간선 DE로 넣습니다. 모든 노드가 트리에 들어와 MST가 완성됩니다.

완료 · MST = AB + BC + CD + DE, 총 가중치 13. Kruskal과 다른 순서로 자랐지만 결과는 같습니다.

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

1 / 7

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