끄적끄적 코딩
article thumbnail
Published 2021. 5. 10. 19:02
프림 알고리즘 (Prim) 자료구조

프림 알고리즘

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법

- 정점선택을 기반으로 하는 알고리즘
- 이전 단계에서 만들어진 신장 트리를 확장하는 방법


동작과정

1. 시작 단계에서는 시작 정점만이 MST집합에 포함
2. 앞 단계에서 만들어진 MST집합에 인접한정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장
   (가장 낮은 가중치를 선택)
3. 위의 과정을 트리가 N-1개의 간선을 가질때까지 반복


시간복잡도

주 반복문이 정점의 수 N만큼 반복하고 내부 반복문이 N번 반복

- 프림 알고리즘의 시간복잡도 O(n^2)
- 그래프에 간선이 많이 존재하는 밀집 그래프에 프림 알고리즘이 적합

검색 태그