프림 알고리즘이란?
최소 신장 트리(MST)을 구현하기 위해 사용되는 알고리즘으로 시작 정점에서부터 정점을 하나씩 추가하며 트리를 확장하는 알고리즘이다.
이 때 연결은 시작 정점으로부터 방문되지 않은 정점들의 가중치 중에서 작은 값들만 찾아 탐색한다.(항상 최적의 해를 찾아서 감)
프림 알고리즘 핵심
- 임의의 정점을 선택한 후 arr에 저장
- 임의의 정점을 방문처리 한 후 연결되어 있는 모든 정점들을 최소 힙에 저장
- 최소 힙에서 가중치 값이 가장 작은 정점 m을 방문 처리한 후 m과 연결되어 있는 방문되지 않은 모든 정점들을 최소 힙에 저장.
- 모든 노드가 visit될 때(최소 힙이 empty일 때)까지 반복.
프림 알고리즘 그림으로 알아보기
다음 그림과 같이 연결된 그래프가 있다.
이 상태에서 임의의 노드부터 시작을 한다.
1번 정점부터 시작해보자.
초기 상태는 어느 정점도 방문하지 않은 상태이고 heap도 비어있다.
1번 정점을 방문하고 1번 정점과 이어져 있는 2, 3번 정점을 heap에 저장한다.
이 때 heap에서 가중치가 가장 작은 값은 4로 3번 정점으로의 연결이다. 3번 정점을 방문한다.
3번 정점을 방문 처리하고 3번 정점과 연결된 2, 4, 5번 정점들을 heap에 저장한다.
(사실 이 때 3번 정점과 연결된 1도 heap에 들어가지만 이미 방문한 정점이므로 조건에서 걸러짐)
heap에서 가중치가 가장 작은 값은 2로 2번 정점이다. 2번 정점을 방문한다.
2번 정점을 방문 처리하고 2번 정점과 연결된 4번 정점을 heap에 저장한다.
heap에서 가중치가 가장 작은 값은 5로 2번 정점과의 연결인데 이미 방문이 된 정점이므로 heap에서 pop만 한다.
그 다음 가중치 최솟값은 6으로 4번 정점을 방문한다.
4번 정점을 방문 처리하고 4번 정점과 연결된 5, 6번 정점을 heap에 저장한다.
그리고 heap에서 가장 작은 가중치 값은 3으로 5번 정점이다. 5번 정점을 방문한다.
5번 정점을 방문 처리하고 5번과 연결된 6번 정점을 heap에 저장한다.
그리고 heap에서 가장 작은 가중치 값은 7로 4번 정점을 방문해야 하는데 이미 방문 처리가 되어있으므로 pop한 후 그 다음 작은 값인 8, 즉 6번 정점으로 연결한다.
이제 모든 정점의 방문이 끝난 상태이다.
더 이상 방문할 정점이 없으니 heap에 남아있는 정점들을 모두 pop하고 종료한다.
소스코드
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> p;
int visited[101];
vector<p> map[30];
int main() {
int N, M, a, b, c, res = 0;
priority_queue <p> pQ;
cin >> N >> M;
for (int i = 1; i <= M; i++) {
cin >> a >> b >> c;
map[a].push_back(make_pair(b, c));
map[b].push_back(make_pair(a, c));
// 정점으로부터 연결 되어있는 정점의 정보 저장(무방향)
}
pQ.push(make_pair(0, 1)); //1번 정점부터 방문
while (!pQ.empty()) {// 최소힙이 비어있다면 종료(모든 정점을 방문했다면)
p temp = pQ.top();
int cost = temp.first * -1;
int v = temp.second;
pQ.pop();
if (!visited[v]) { //방문되지 않은 정점
visited[v] = 1; //방문처리하고 결과값에 가중치 더하기
res += cost;
for (int i = 0; i < map[v].size(); i++) {
pQ.push(make_pair(map[v][i].second * -1, map[v][i].first));
//현재 정점과 연결된 모든 정점을 힙에 저장
}
}
}
cout << res;
return 0;
}