프림 알고리즘(최소신장트리, MST, prime)

 

---

목차

---

최소 신장 트리 (MST, Minimum Spanning Tree) 

그래프 내의 모든 정점을 포함하면서 사용된 간선들의 가중치 합이 최소가 되는 트리 

 

MST 특징

1) 간선(Edge)의 가중치 합이 최소

2) N개의 정점을 가지는 그래프에서 반드시 (N - 1) 개의 간선만을 사용해야 함 (= 트리의 성질)

3) Cycle을 포함하면 안된다

 

프림(Prime) 알고리즘 

- 인접 리스트와 우선 순위 큐, 그리고 방문 배열을 사용

- 시작점을 기준으로 인접한 정점 중에 아직 연결하지 않았고, 가중치가 최소인 정점을 선택 반복하여 노드를 연결함

- 우선 순위 큐를 집합으로 보고, 가장 가중치가 작은 노드를 우선 순위로 하여 연결(=방문) 여부 확인 후 연결 처리 한다.

- 시간 복잡도 : O((V + E)logV) = O(ElogV)

 

- 우선 순위 큐에서 최소 힙으로 정렬하기 때문에 logV^2 만큼의 시간이 소비됨 (=최대 간선의 개수는 정점 제곱 이하)
2logV 에서 상수 생략 되어 logV 남음
- 인접리스트 그래프 순회는 O(V + E)만큼 소요

 

 

절차

1) 간선의 정보를 인접 리스트로 나타냄 (양방향 그래프로 표현)

2) 프림 알고리즘 수행 

2-1) 시작 노드에 대한 정보를 PriorityQueue에 추가 (최소힙, 간선 가중치 기준 오름차순 정렬)

2-2) 연결 여부 확인 

이미 연결된 경우 - continue
연결되지 않은 경우 - 방문처리 후, 비용 합산, 연결 노드 조회

3) 해당 노드에 연결된 노드 중에 아직 방문하지 않은 경우 우선 순위 큐에 추가

4) 2~3번까지 과정 반복하며 사이클 형성되지 않는 MST 최소 비용 구함 

 

 

참고. 크루스칼 알고리즘 (사용하는 자료 구조 잘 구분하기)

크루스칼 알고리즘 (MST, 최소 신장 트리, kruskal)

 

 

프림 알고리즘 예시

위키 백과 참고

 

1) 초기화 , A 노드 시작

- 양방향 그래프로 생각하고 인접 리스트 초기화 

- 시작 노드를 A로 해서 PriorityQueue에 추가

- 처음 방문 했기 때문에 visit[] 방문 처리 후 비용 합산 ( 총 비용 : 0 )

- A노드에 연결된 노드 중 아직 방문하지 않은 노드 D, B 정보를 PriorityQueue에 추가

2) D 노드 

- PriorityQueue에서 비용이 가장 작은 D노드 정보를 꺼냄

- 처음 방문 했기 때문에 visit[] 방문 처리 후 비용 합산 ( 총 비용 : 0 + 5 = 5 ) 

- D노드에 연결된 노드 중 아직 방문하지 않은 노드 B, E, F 정보를 PriorityQueue에 추가

A노드의 경우 시작노드로 이미 방문 처리 되었기 때문에 추가되지 않음

 

3) F 노드 

- PriorityQueue에서 비용이 가장 작은 F노드 정보를 꺼냄

- 처음 방문 했기 때문에 visit[] 방문 처리 후 비용 합산 ( 총 비용 :  5 + 6 = 11 ) 

- F노드에 연결된 노드 중 아직 방문하지 않은 노드 E, G 정보를 PriorityQueue에 추가

 

4) B 노드 

- PriorityQueue에서 비용이 가장 작은 B노드 정보를 꺼냄

- 처음 방문 했기 때문에 visit[] 방문 처리 후 비용 합산 ( 총 비용 :  11 + 7 = 18 ) 

- B노드에 연결된 노드 중 아직 방문하지 않은 노드 C, D, E 정보를 PriorityQueue에 추가

 

5) E 노드 

- PriorityQueue에서 비용이 가장 작은 E노드 정보를 꺼냄

- 처음 방문 했기 때문에 visit[] 방문 처리 후 비용 합산 ( 총 비용 :  18 + 7 = 25 )

- E노드에 연결된 노드 중 아직 방문하지 않은 노드 C, G 정보를 PriorityQueue에 추가

 

6) C 노드 

- PriorityQueue에서 비용이 가장 작은 C노드 정보를 꺼냄

- 처음 방문 했기 때문에 visit[] 방문 처리 후 비용 합산 ( 총 비용 :  25 + 5 = 30 )

- C노드에 연결된 노드 중 아직 방문하지 않은 노드 없으므로 PriorityQueue에 추가 정보 없음

7) 이미 방문한 E, C, B continue 처리 

- 앞서 최소 비용으로 E, C, B노드를 방문 처리함 (= 가치가 없다)

- 순차적으로 PriorityQueue에서 꺼낸 후 방문 여부 확인 조건문 통해 continue 처리 

 

8) G 노드 

- PriorityQueue에서 비용이 가장 작은 G노드 정보를 꺼냄

- 처음 방문 했기 때문에 visit[] 방문 처리 후 비용 합산 ( 총 비용 :  30 + 9 = 39 )

- G노드에 연결된 노드 중 아직 방문하지 않은 노드 없으므로 PriorityQueue에 추가 정보 없음

 

- PriorityQueue에 남은 나머지 정보도 마찬가지로 이미 방문 처리 되어 있어서, continue 처리됨 

- 총 39 비용으로 MST 형성

 

 

백준 추천 문제

1. 불우이웃돕기(골드3)

2. 별자리 만들기(골드3)

3. 물대기(골드2)

 

풀이 참고 

https://dev-ljw1126.tistory.com/365

[BOJ1414] 불우이웃돕기 (프림, 최소 신장트리, 그리디)

https://dev-ljw1126.tistory.com/366

[BOJ4386] 별자리 만들기 (프림 알고리즘, 최소신장트리, MST)

https://dev-ljw1126.tistory.com/367

[BOJ1368] 물대기 (프림 알고리즘, 최소 신장 트리, 그리디)