[알고리즘]프림 알고리즘(Prim'a Algorithm)

최소 신장 트리를 만들어 내는 과정

1. 그래프와 최소 신장 트리를 준비. 이때의 최소 신장트리는 노드가 하나도 없는 상태

2. 그래프에서 임의의 정점을 시작 정점으로 선택하여 최소 신장 트리의 루트 노드로 삽입한다.

3. 삽입되어 있는 정점들과 모든 인접 정점 사이에 있는 간선의 가중치를 조사. 간선 중 가장 가중치가 작은 것을 골라 이 간선에 연결되어 있는 인접 정점을 최소 신장트리에 삽입. 단, 새로 삽입되는 정점은 최소 신장트리에 삽입되어 있는 기존의 노드들과 사이클을 형성 하면 안됨.

4. 3의 과정을 반복하다가 최소 신장 트리가 그래프의 모든 정점을 연결하게 되면 알고리즘 종료

 

예제

위와 같은 그래프가 있다.

 

여기서 임의의 정점 B를 시작으로 루트로 정해보자.

 

그 주위에 정점 A F C 로 가는 간선 가중치 중 가장 작은 35 A와 연결 해준다.

 

 

그 다음으로 A-E / B-F / B-C 중 가장 적은 가중치 126을 가진 C와 연결해준다.

 

그다음 으로 작은 C-D 117과 연결해주고, F와 C는 사이클이 형성됨으로 제외 되고 그 F 와 근접한 E 와 D H 중 가장 작은 E와 연결이 된다. 이런식으로 사이클 형성은 되지 않으며 가장 작은 가중치 값들을 이어 나간다.

 

이렇게 하여 최소 신장트리가 완성 되었다.

 

 

사용 할수 있는 자료 구조 : 배열/링크드리스트/ 트리/ 그래프 

최소 가중치를 골라내는 과정에서 발생하는 성능 문제가 제법 심각하다. 해결하는 방법으로는 정점이 추가 될 때마다 조사 대상 간선 정렬하기와 이진 탐색트리에 조사 대상 간선 입력하기 등이 있겠지만, 우선순위 큐 사용이 삽입 삭제과 빠르며 최소값 찾는데 비용이 거의 들지 않으므로 추천한다.