[알고리즘] 프림(Prim) 알고리즘

💡프림(Prim) 알고리즘이란?

프림(Prim) 알고리즘 특

• 최소 신장 트리 알고리즘
• 노드를 중심으로 간선 탐색
• 배열로 구현할 경우 시간 복잡도 $O(n^2)$, 우선 순위 큐로 구현할 경우 시간 복잡도 $O(ElogN)$
• 그리디 알고리즘

알고리즘 과정

1. 임의의 노드를 선택
2. 해당 노드와 연결되어 있는 간선 중 가중치가 최소인 것을 MST에 추가
3. MST에 포함된 모든 정점과 연결된 간선 중 가중치가 최소이고, 사이클을 형성하지 않는 것을 MST에 추가
4. V-1개의 간선이 선택될 때까지 간선 선택을 반복

과정 예시

1. 초기 상태

2. 노드 1 선택

노드 1과 연결된 세 개의 간선 우선 순위 큐 추가

 

 

 

 

 

 

 

 

 

 

 

 

우선 순위 큐 

1

5

7

 

 

 

3. 큐에 포함된 간선 중 가장 작은 간선 선택 후 MST에 연결 노드 3 추가

MST에 포함된 모든 간선 큐에 삽입

 

 

 

 

 

 

 

 

 

 

 

우선 순위 큐

4

5

7

9

 

 

 

 

4. MST에 포함된 간선 개수가 N-1개가 될 때까지 선택 과정을 반복

단, 사이클 발생 시 해당 간선은 포함될 수 없음

 

5. 완성된 최소 스패닝 트리