[C++] Prim 알고리즘 ( 최소 신장 트리, MST 알고리즘 )

프림( Prim ) 알고리즘

프림 알고리즘은 최소 신장 트리( MST, Mimimal Spanning Tree )를 구하는 알고리즘입니다.

최소 신장 트리는 주어진 그래프에서 최소의 가중치를 가진, 모든 노드를 지나는 트리를 말합니다.

 

 

최소 신장 트리( Minimal Spanning Tree )

 

이러한 알고리즘으로는 크루스칼( Kruskak ) 알고리즘이 있습니다.

최소 신장 트리와 크루스칼 알고리즘에 관한 내용은 여기서 볼 수 있습니다.

[C++] Kruskal 알고리즘 ( 최소 신장 트리, MST 알고리즘 )

 

이 글에서는, 위의 글에서 설명했던 예와 같은 예를 사용하기 때문에, 크루스칼 알고리즘이 처리하는 방식과 프림 알고리즘의 방식을 비교해 볼 수 있을 것입니다.

 

프림 알고리즘이 최소 신장 트리는 구하는 과정은 다음과 같습니다.

 

1. 임의의 정점을 선택합니다.
2. 선택한 정점에 연결된 간선을 이루는 반대편 정점과 가중치를 버퍼에 저장합니다.
3. 위 버퍼에서 가장 작은 가중치를 가진 정점을 선택해서 트리에 추가합니다.
4. 선택한 정점의 개수가 모든 정점의 개수와 같아질 될 때까지 2의 과정을 반복합니다.

 

위의 과정을 다음 그래프에 적용하면 다음과 같습니다.

 

가중치가 있는 그래프

 

먼저, 임의의 정점으로부터 트리를 시작합니다.

이 글에선 정점 1부터 시작합니다.

그리고, 정점 1과 연결된 정점 2와 정점 3중 가중치가 낮은 정점 2를 선택합니다.

(정점 3과 가중치 12는 버퍼에 저장 )

 

 

 

그다음, 선택된 정점 2에 연결된 정점 3, 4 중에서 가중치가 낮은 정점 3을 선택합니다.

(정점 4와 가중치 11은 버퍼에 저장 )

 

 

선택된 정점 3과 연결된 4, 5 중에서 가중치가 낮은 정점 4를 선택합니다.

(정점 5와 가중치 5는 버퍼에 저장 )

 

 

 

선택된 정점 4에 연결된 정점 5는 가중치가 8,

버퍼에 있는 정점 3에 연결된 정점 5는 가중치가 5이므로,

가중치 5인 간선을 선택합니다.

 

 

 

그래서, 선택한 정점 5까지 해서 모든 정점을 포함했으므로, 트리 구성을 종료합니다.

이 트리가 최소 신장 트리( MST )입니다.

 

최소 신장 트리( MST )

 

 

이 과정을 구현하기 위해, 내림차순( 최소 힙 ) 우선순위 큐( priority queue )를 사용합니다.

내림차순 우선순위 큐는 가장 작은 값을 가진 원소가 최상위에 위치합니다.

 

우선순위 큐는 입력된 원소들을 자동으로 정렬하므로,

위의 가중치를 가진 정점들을 저장함과 동시에 정렬되어, 최상위에 위치하는, 가장 낮은 가중치를 가진 정점을 손쉽게 가져올 수 있는 장점이 있습니다.

 

그리고, 같은 정점을 다시 방문하지 않도록 visited 배열을 사용했습니다.

Kruskal 알고리즘은 Union Find 알고리즘을 사용해서, 순환 경로가 생기지 않도록 한 반면,

Prim 알고리즘은 이 플래그 배열을 사용해서 순환 경로를 방지를 하고 있습니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define VERT_SIZE   5

typedef pair<int, int> V_WEIGHT;

vector<V_WEIGHT> graph[VERT_SIZE+1];	// 정점에 연결된 정점과 가중치 저장
bool visited[VERT_SIZE+1];

void AddEdge( int s, int e, int weight){
    graph[s].emplace_back(e, weight);
    graph[e].emplace_back(s, weight);
}

struct Compare{
    bool operator()( const V_WEIGHT& d1, const V_WEIGHT& d2) const{   // 내림차순 (최소 힙)
        return d1.second > d2.second;
    }
};

int main(){

    AddEdge(1, 2, 1); // 간선 추가 ( 정점 1,2와 가중치 1 )
    AddEdge(1, 3, 12);
    AddEdge(2, 3, 10);
    AddEdge(2, 4, 11);
    AddEdge(3, 4, 2);
    AddEdge(3, 5, 5);
    AddEdge(4, 5, 8);
    
    priority_queue<V_WEIGHT, vector<V_WEIGHT>, Compare> pq; 

    int nTotalWeight = 0;
    pq.emplace(1, 0);   // 1번 정점부터 시작

    while( !pq.empty()){
        
        V_WEIGHT vw = pq.top();	// 가장 작은 가중치를 가진 정점 선택
        pq.pop();

        int vert = vw.first;

        if ( !visited[vert]){   // 아직 도달하지 않는 정점만 추가

            nTotalWeight += vw.second;
            visited[vert] = true;

            // 현재 정점에 연결된 정점과 가중치 저장
            for( const V_WEIGHT& x : graph[vert]){
                if ( !visited[x.first]){
                    pq.push(x);	// 가중치가 내림차순으로 자동 정렬됨
                }
            }
        }
    }

    cout << nTotalWeight;   // MST의 가중치 출력

    return 0;
}