Prim 알고리즘

Prim 알고리즘

한 정점에서 시작하여 인접 최소 가중치 간선을 반복 추가하여 MST를 구성하는 탐욕 알고리즘

특징: 정점 기반, 우선순위 큐, Dijkstra와 유사 구조

동작: 시작 정점 선택(key=0) → 최소 key 정점 추출 → 인접 정점 key 갱신(weight

Dijkstra와 차이: Dijkstra는 누적 거리(dist+w) 기준, Prim은 간선 가중치(w) 자체 기준

시간 복잡도: 배열 O(V², 밀집 적합) / 이진 힙 O((V+E)log V) / 피보나치 힙 O(E+V log V)

Kruskal vs Prim 비교

• •Kruskal: 간선 기반, Union-Find, O(E log E), 희소 그래프 유리, 비연결 자동 처리
• •Prim: 정점 기반, 우선순위 큐, O(V²) 또는 O((V+E)log V), 밀집 그래프 유리

적용사례: 네트워크 설계, 밀집 그래프, 클러스터링

연관: MST, Kruskal, 우선순위 큐, 탐욕, Dijkstra