프림 알고리즘 편집하기

'''프림 알고리즘'''(Prim's Algorithm)은 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 알고리즘 중 하나로, '''그리디 알고리즘'''(Greedy Algorithm)에 기반하여 동작한다. 크루스칼 알고리즘과 달리, '''정점 중심(Vertex-based)'''으로 동작하며, 한 정점에서 시작하여 최소 비용으로 트리를 확장해 나간다.
==개요==
프림 알고리즘은 다음과 같은 방식으로 동작한다.
*1. 임의의 정점에서 시작하여 최소 신장 트리에 포함.
*2. MST에 포함된 정점과 연결된 간선 중 최소 가중치 간선을 선택하여 추가.
*3. 사이클이 형성되지 않도록 유의하면서 모든 정점이 포함될 때까지 반복.
이 과정에서 '''우선순위 큐(Priority Queue)'''를 사용하면 효율적으로 최소 비용 간선을 선택할 수 있다.
==동작 과정==
다음 그래프를 예로 들어 프림 알고리즘의 동작을 살펴보자.
  '''그래프''' (정점: 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)
#초기 정점 선택: A
#*MST: {A}
#*선택 가능한 간선: (A-B, 7), (A-D, 5)
#*최소 가중치 간선 (A-D, 5) 선택
#두 번째 단계:
#*MST: {A, D}
#*선택 가능한 간선: (A-B, 7), (D-F, 6), (D-E, 15)
#*최소 가중치 간선 (D-F, 6) 선택
#세 번째 단계:
#*MST: {A, D, F}
#*선택 가능한 간선: (A-B, 7), (D-E, 15), (F-G, 11), (E-F, 8)
#*최소 가중치 간선 (A-B, 7) 선택
#모든 정점이 연결될 때까지 이 과정을 반복하여 최소 신장 트리를 생성.
==코드 예제==
<syntaxhighlight lang="python">
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)
</syntaxhighlight>
 출력 결과 예시:
 [(3, 5), (5, 6), (4, 5), (0, 7), (1, 8), (2, 9)]
==시간 복잡도==
프림 알고리즘의 시간 복잡도는 다음과 같다.
*인접 리스트 + 우선순위 큐(힙) 사용 → '''O((V + E) log V)'''
*인접 행렬 사용 → '''O(V²)'''
우선순위 큐를 사용하면 크루스칼 알고리즘(O(E log E))보다 효율적인 경우가 많다.
==응용==
프림 알고리즘은 여러 분야에서 활용된다.
*'''네트워크 설계''' → 최소 비용으로 네트워크 구축
*'''도로망 설계''' → 최소한의 도로로 모든 도시 연결
*'''전력망 설계''' → 최소 전선 길이로 모든 지역 연결
==같이 보기==
*[[최소 신장 트리]]
*[[크루스칼 알고리즘]]
*[[다익스트라 알고리즘]]
==참고 문헌==
*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.
[[분류:알고리즘]]
[[분류:트리 이론]]
[[분류:그래프 이론]]
설명	입력하는 내용	문서에 나오는 결과
기울임꼴	''기울인 글씨''	기울인 글씨
굵게	'''굵은 글씨'''	굵은 글씨
굵고 기울인 글씨	'''''굵고 기울인 글씨'''''	*굵고 기울인 글씨*