최소 스패닝 트리 (MST) : 프림 알고리즘 (Prim Algorithm)

최소 스패닝 트리에 대한 내용과 크루스칼 알고리즘은 아래 포스팅에서 확인할 수 있다.

최소 스패닝 트리 (MST) : 크루스칼 알고리즘 (Kruskal Algorithm)

 

프림 알고리즘 (Prim Algorithm)

프림 알고리즘은 최소 스패닝 트리(MST)를 구하는 알고리즘으로, 다음과 같이 동작한다.

① 최초 출발 노드와 연결되어 있는 간선들 중 가중치가 최소인 것을 선택해 MST에 추가한다. 이제 MST에는 2개의 정점이 포함되어 있다.

② MST에 포함된 모든 정점들과 연결된 간선들 중 가중치가 최소인 것을 선택해 MST에 추가한다.

③ V - 1개의 간선이 선택될 때까지 ②를 반복한다.

이제 크루스칼 알고리즘에서 살펴봤던 예제 그래프를 통해, 자세한 동작 원리를 알아보자.

예제 그래프에서 출발 노드는 1번이라 가정한다.

예제 그래프

현재 MST에는 출발 노드인 1번 정점만 포함된 상태이다.

MST의 모든 정점에 대해, 연결되어 있는 간선을 파란 실선으로 나타내면 위와 같다. 

 

 

이들 중, 최소 가중치인 1, 5번 정점을 잇는 간선을 선택한다.

이제 MST에는 1, 5번의 두 정점이 포함된다.

이제 MST의 모든 정점과 연결된 간선은 위와 같아진다. 이제 이들 중 다시 최소인 간선을 선택한다.

이제 이와 같은 과정을 V - 1개의 간선이 선택될 때까지 반복한다.

 

Prim 알고리즘은 Kruskal 알고리즘과 다르게 정점을 중심으로 동작하므로, 그래프 탐색과 유사하게 동작한다.

즉, 인접 리스트를 사용한 정점들 간의 연결 관계가 필요하며, 이미 방문한 정점들에 대한 visit 정보를 기록한다.

각 정점들과 연결된 간선들 중 최소인 간선을 선택하는 데에 우선순위 큐를 사용한다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
typedef pair<int, int> p;
 
int v = 6;
vector<p> adj[7];
bool visit[7];
 
//우선순위 큐 정렬함수
struct compare {
    bool operator()(p a, p b) {
        return a.second > b.second;
    }
};
 
void Prim() {
    //큐 안의 간선들은 가중치 기준 오름차순으로 항상 정렬됨
    priority_queue<p, vector<p>, compare> pque;
 
    //출발지와 연결된 간선들을 모두 큐에 삽입
    for (int i = 0; i < adj[1].size(); i++) pque.push(adj[1][i]);
    visit[1] = true;
 
    int cnt = 0;
    while (cnt < v - 1) {
        p curline = pque.top();
        pque.pop();
 
        int node = curline.first;
        int weight = curline.second;
 
        //뽑은 간선의 목적지 노드가 이미 발견된 상태라면 선택하지 않음
        if (visit[node]) continue;
        visit[node] = true;
        cnt++;
 
        //현재 간선을 MST에 추가
        printf("%d번 정점 발견 : 비용 %d\n", node, weight);
 
        //뽑은 간선의 목적지 노드와 연결된 간선들을 모두 큐에 삽입
        for (int i = 0; i < adj[node].size(); i++) {
            int nextnode = adj[node][i].first;
            if (!visit[nextnode]) pque.push(adj[node][i]);
        }
    }
}
 
void init() {
    adj[1].push_back({ 2, 9 });
    adj[1].push_back({ 3, 4 });
    adj[1].push_back({ 4, 3 });
    adj[1].push_back({ 5, 1 });
 
    adj[2].push_back({ 1, 9 });
    adj[2].push_back({ 4, 4 });
    adj[2].push_back({ 5, 5 });
 
    adj[3].push_back({ 1, 4 });
    adj[3].push_back({ 6, 6 });
 
    adj[4].push_back({ 1, 3 });
    adj[4].push_back({ 2, 4 });
    adj[4].push_back({ 5, 2 });
    adj[4].push_back({ 6, 8 });
 
    adj[5].push_back({ 1, 1 });
    adj[5].push_back({ 2, 5 });
    adj[5].push_back({ 4, 2 });
 
    adj[6].push_back({ 3, 6 });
    adj[6].push_back({ 4, 8 });
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
 
    printf("[MST]\n");
    Prim();
 
    return 0;
}