Prim 알고리즘

Intro

• Prim 알고리즘의 이해

Prim 알고리즘

프림 알고리즘은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 신장 트리를 생성하는 알고리즘이다. ¹

동작 순서

1. 시작 정점 하나를 집합에 포함한다.

2. 앞 단계에서 만들어진 MST(최소 비용 신장 트리) 집합에 인접한 정점들중 가장 낮은 가중치로 트리 확장

3. 위의 과정을 트리가 (N-1) 간선을 가질 때 까지 반복

예제

Prim 알고리즘의 시간복잡도

인접 행렬과 최소 비용값이 들어있는 배열에서 최소 비용값을 찾는 검색을 할경우 시간 복잡도는 O(N²)

이진 힙과 인접 리스트 표현을 사용하면 O(ElogV)내에 수행된다. (E=변 갯수, V=꼭지점 갯수)

피보나치 힙을 사용한다면 O(E+VlogV)로 시간복잡도가 감소 한다.

참고자료

Heee’s 블로그

1. 위키백과 ↩