프림 알고리즘

프림 알고리즘(Prim's Algorithm)은 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 알고리즘 중 하나로, 그리디 알고리즘(Greedy Algorithm)에 기반하여 동작한다. 크루스칼 알고리즘과 달리, 정점 중심(Vertex-based)으로 동작하며, 한 정점에서 시작하여 최소 비용으로 트리를 확장해 나간다.

1 개요

프림 알고리즘은 다음과 같은 방식으로 동작한다.

• 1. 임의의 정점에서 시작하여 최소 신장 트리에 포함.
• 2. MST에 포함된 정점과 연결된 간선 중 최소 가중치 간선을 선택하여 추가.
• 3. 사이클이 형성되지 않도록 유의하면서 모든 정점이 포함될 때까지 반복.

이 과정에서 우선순위 큐(Priority Queue)를 사용하면 효율적으로 최소 비용 간선을 선택할 수 있다.

2 동작 과정

다음 그래프를 예로 들어 프림 알고리즘의 동작을 살펴보자.

 그래프 (정점: A, B, C, D, E, F, G)
 간선 리스트:  
 (A-B, 7), (A-D, 5), (B-C, 8), (B-D, 9), (B-E, 7),  
 (C-E, 5), (D-E, 15), (D-F, 6), (E-F, 8), (E-G, 9), (F-G, 11)

1. 초기 정점 선택: A
   • MST: {A}
   • 선택 가능한 간선: (A-B, 7), (A-D, 5)
   • 최소 가중치 간선 (A-D, 5) 선택
2. 두 번째 단계:
   • MST: {A, D}
   • 선택 가능한 간선: (A-B, 7), (D-F, 6), (D-E, 15)
   • 최소 가중치 간선 (D-F, 6) 선택
3. 세 번째 단계:
   • MST: {A, D, F}
   • 선택 가능한 간선: (A-B, 7), (D-E, 15), (F-G, 11), (E-F, 8)
   • 최소 가중치 간선 (A-B, 7) 선택
4. 모든 정점이 연결될 때까지 이 과정을 반복하여 최소 신장 트리를 생성.

3 코드 예제

import heapq

def prim(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v, weight in edges:
        graph[u].append((weight, v))
        graph[v].append((weight, u))

    mst = []
    visited = set()
    pq = [(0, 0)]  # (가중치, 정점)
    
    while len(visited) < n:
        weight, node = heapq.heappop(pq)
        if node in visited:
            continue
        visited.add(node)
        mst.append((node, weight))
        
        for next_weight, neighbor in graph[node]:
            if neighbor not in visited:
                heapq.heappush(pq, (next_weight, neighbor))

    return mst[1:]  # 루트 노드(0)의 가중치는 제외

# 예제 그래프 (정점 0~6)
edges = [
    (0, 1, 7), (0, 3, 5), (1, 2, 8), (1, 3, 9), (1, 4, 7),
    (2, 4, 5), (3, 4, 15), (3, 5, 6), (4, 5, 8), (4, 6, 9), (5, 6, 11)
]

mst = prim(7, edges)
print(mst)

출력 결과 예시:
[(3, 5), (5, 6), (4, 5), (0, 7), (1, 8), (2, 9)]

4 시간 복잡도

프림 알고리즘의 시간 복잡도는 다음과 같다.

• 인접 리스트 + 우선순위 큐(힙) 사용 → O((V + E) log V)
• 인접 행렬 사용 → O(V²)

우선순위 큐를 사용하면 크루스칼 알고리즘(O(E log E))보다 효율적인 경우가 많다.

5 응용

프림 알고리즘은 여러 분야에서 활용된다.

• 네트워크 설계 → 최소 비용으로 네트워크 구축
• 도로망 설계 → 최소한의 도로로 모든 도시 연결
• 전력망 설계 → 최소 전선 길이로 모든 지역 연결

6 같이 보기

• 최소 신장 트리
• 크루스칼 알고리즘
• 다익스트라 알고리즘

7 참고 문헌

• Prim, Robert C. "Shortest connection networks and some generalizations." Bell System Technical Journal, 1957.
• Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.