프림 알고리즘 (Prim’s Algorithm)
프림 알고리즘이란
프림 알고리즘은 정점 중심의 탐욕 알고리즘으로 최소 신장 트리를 구하는 방법으로, 시작 정점에서 출발하여 현재 트리와 연결된 간선 중 최소 가중치를 가진 간선을 선택하며 트리를 확장해 나가는 알고리즘이다.
알고리즘 시각화
동작 예시
아래와 같은 그래프가 주어졌을 때 프림 알고리즘의 동작 과정을 살펴보자.
(A)
2/ \3
(B) (C)
1\ /4
(D)1단계: 시작 정점 선택
임의의 정점을 시작점으로 선택한다. (여기서는 A 선택)
선택: [A]
2단계: 정점 확장
현재 트리와 연결된 간선 중 최소 가중치를 가진 간선을 선택하여 정점을 추가한다.
- A-B(2) 선택 → MST: [A-B]
- B-D(1) 선택 → MST: [A-B, B-D]
- A-C(3) 선택 → MST: [A-B, B-D, A-C]
3단계: 완성
- 선택된 간선: 3개 (V-1 = 4-1 = 3)
- 최소 가중치 합: 2 + 1 + 3 = 6
복잡도
| 구분 | 복잡도 | 설명 |
|---|---|---|
| 시간 복잡도 | O(E log V) | - 정점 선택 및 방문: O(V) - 우선순위 큐 삽입: O(E log V) - 우선순위 큐 추출: O(V log V) |
| 공간 복잡도 | O(V + E) | - 그래프 표현: O(V + E) - 방문 배열: O(V) - 우선순위 큐: O(E) |
장단점
| 장점 | 단점 |
|---|---|
| 밀집 그래프에 유리 - 간선이 많을 때 효율적 - O(E log V)는 E가 클 때 유리 | 시작 정점 필요 - 임의의 정점 선택 필요 - 연결되지 않은 그래프는 처리 불가 |
| 정점 중심 탐색 - 시작 정점에서 점진적 확장 - 트리 구조를 명확히 파악 | 우선순위 큐 구현 필요 - 별도의 자료구조 구현 필요 - 구현 복잡도 증가 |
주의사항
- 그래프가 연결되어 있어야 MST 존재
- 방문한 정점은 다시 처리하지 않도록 체크
- 0-indexed vs 1-indexed 주의
- 간선이 적으면 크루스칼 알고리즘 고려
- 임의 정점에서 시작해도 최소 비용은 동일하지만, 선택되는 간선은 다를 수 있음
Last updated on