[ 프림 알고리즘 ] 개념과 구현방법(2) (C++)

이번 글에서는 프림 알고리즘을 직접 구현해보는 방법에 대해서 알아보겠습니다.

먼저, 프림 알고리즘이 무슨 알고리즘인지 잘 모르시는 분들은 먼저 아래의 글을 읽고 오는 것을 권장드립니다.

[ 프림 알고리즘에 대해서 알아보기(Click) ]

3. 프림 알고리즘 구현하기

먼저 프림 알고리즘을 구현하는 방법은 일반적으로 크게 2가지 방법이 있다.

첫 번째 방법은, 이전의 프림 알고리즘에 대해서 설명한 글에서 처럼, Dist[] 배열을 하나 선언해서, 정점을 하나씩

선택할 때 마다, 최단길이인 간선을 찾아서 정점간의 길이를 업데이트를 해주면서 진행하는 방법이다.

두 번째 방법은, 자료구조 힙을 이용해서 구현하는 방법이 있는데 이 방법은 차근차근 알아가 보도록 하자.

먼저 첫 번째 방법부터 알아보자.

지난 번 글에서 프림 알고리즘이 동작하는 순서는 다음과 같다고 했다.

1. 임의의 시작점 하나를 선택한다.

  2. 이 시작점과 연결된 정점들의 거리를 업데이트 한다.

  3. 선택된 정점들과 연결되어 있는 간선들 중에서, 가장 짧은 길이의 간선을 선택해서 연결해준다.

  4. 가장 짧은 간선으로 연결되어 있는 정점을 선택하고, 정점들의 거리를 업데이트 한다.

  5. 3 ~ 4 번의 과정은 N(전체 노드의 갯수) - 1번 만큼 반복해준다.

출처: https://yabmoons.tistory.com/362?category=838490 [얍문's Coding World..]

1. 임의의 시작점 하나를 선택한다.

2. 이 시작점과 연결된 정점들의 거리를 업데이트 한다.

3. 선택된 정점들과 연결되어 있는 간선들 중에서, 가장 짧은 길이의 간선을 선택해서 연결해준다.

4. 가장 짧은 간선으로 연결되어 있는 정점을 선택하고, 정점들의 거리를 업데이트 한다.

5. 3 ~ 4번의 과정을 N(전체 노드의 갯수) - 1 번 만큼 반복해준다.

먼저 1 ~ 2 번에 대한 코드이다.

Dist[1] = 0;
Select[1] = true;
for (int i = 0; i < Cost[1].size(); i++)
{
    int Next = Cost[1][i].first;
    int Distance = Cost[1][i].second;
    Dist[Next] = Distance;
}

임의의 시작점, 가장 무난하게 1번 정점을 선택했다고 가정했을 경우이다.

Dist 배열의 초기 값은 모두 INF(무한대)로 설정이 되어있다. 이 때, 1번을 선택했으므로 1번까지의 거리 = 0 으로 업데이트

해주고, 1번을 선택한 정점이라고 표시해주는 것이다.

그 후, 2번과정을 진행한 것이다.

1번 정점과 연결되어 있는 정점들의 Dist배열 값을 무한대에서 간선의 길이로 업데이트 해 주었다.

이 후 3 ~ 5번의 과정에 대한 코드이다.

for (int i = 1; i <= N - 1; i++)
{
    int Min_Cost = INF;
    int Min_Idx = -1;
    for (int j = 1; j <= N; j++)
    {
        if (Select[j] == true) continue;
        if (Min_Cost > Dist[j])
        {
            Min_Cost = Dist[j];
            Min_Idx = j;
        }
    }
    Select[Min_Idx] = true;
    Answer = Answer + Min_Cost;
 
    for (int j = 0; j < Cost[Min_Idx].size(); j++)
    {
        int Next = Cost[Min_Idx][j].first;
        int Distance = Cost[Min_Idx][j].second;
        if (Select[Next] == true) continue;
        if (Dist[Next] > Distance) Dist[Next] = Distance;
    }
}

지금부터는 line by line으로 코드에 대해서 설명을 해보겠다.

line1)

- 5번과정에서 말했듯이, 총 N - 1번의 탐색을 실시해 주어야 한다.

  따라서, 1 ~ N - 1 까지만 반복하면서 진행

line3 ~ 13)

- 3번 과정을 나타낸 부분이다. 전체 N개의 노드를 탐색하면서, 현재 선택된 정점들(빨간색 동그라미)과 거리를

  측정했을 때, 가장 짧은 길이의 간선을 찾는 과정이다.

  정상적으로 가장 길이가 짧은 간선을 찾았다면, Min_Cost 값에는 가장 짧은 간선의 길이가, Min_Idx에는 정점의

  번호가 저장되어 있을 것이다.

  하지만, 만약 Min_Cost에 무한대 값이 그대로 들어있거나, Min_Idx값에 초기 설정값인 -1이 들어있다면 ??

  이는, 모든 정점이 연결된 연결 그래프가 아니라는 것을 의미한다.

line14 ~ 15)

- 4번 과정에서 "가장짧은 간선으로 연결되어 있는 정점을 선택하고" 에 해당하는 부분이다.

  Select배열에 해당 정점을 선택한다고 표시해주고 있고,

  15번 라인에서는 Answer이라는 변수에 해당 경로의 길이를 더하고 있는데, 이는 최소 스패닝 트리의 총 길이를

  구하기 위해서 더해주고 있는 것이다.

line17 ~ 23)

- 4번과정에서 "정점들의 거리를 업데이트 한다" 에 해당하는 부분이다.

  선택된 정점이 하나 추가된다면, 해당 정점에 의해서 길이가(Dist배열의 값이) 갱신되는 정점들이 분명히 존재했다.

  해당 과정을 진행하고 있는 부분이다.

[ 전체 소스코드 ]

int N, M, Answer;
int Dist[MAX];
bool Select[MAX];
vector<pair<int, int>> Cost[MAX];
 
void Prim()
{
    Dist[1] = 0;
    Select[1] = true;
    for (int i = 0; i < Cost[1].size(); i++)
    {
        int Next = Cost[1][i].first;
        int Distance = Cost[1][i].second;
        Dist[Next] = Distance;
    }
 
    for (int i = 1; i <= N - 1; i++)
    {
        int Min_Cost = INF;
        int Min_Idx = -1;
        for (int j = 1; j <= N; j++)
        {
            if (Select[j] == true) continue;
            if (Min_Cost > Dist[j])
            {
                Min_Cost = Dist[j];
                Min_Idx = j;
            }
        }
 
        Select[Min_Idx] = true;
        Answer = Answer + Min_Cost;
 
        for (int j = 0; j < Cost[Min_Idx].size(); j++)
        {
            int Next = Cost[Min_Idx][j].first;
            int Distance = Cost[Min_Idx][j].second;
 
            if (Select[Next] == true) continue;
            if (Dist[Next] > Distance) Dist[Next] = Distance;
        }
    }
}
 

두 번째 방법은 첫 번째 방법에서 사용한 Dist[] 배열을 사용하지 않고, 자료구조 힙을 사용해서 구현하는 방법이다.

일반적으로, Priority_Queue를 이용해서 구현한다.

먼저 코드를 보고 구체적으로 알아보자.

void Prim_Using_Heap()
{
    priority_queue<pair<int, int>> PQ;
    for (int i = 0; i < Cost[1].size(); i++)
    {
        int Next = Cost[1][i].first;
        int Distance = Cost[1][i].second;
        
        PQ.push(make_pair(-Distance, Next));
    }
    
    Visit[1] = true;
    while (PQ.empty() == 0)
    {
        int Distance = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        if (Visit[Cur] == false)
        {
            Visit[Cur] = true;
            Answer = Answer + Distance;
            for (int i = 0; i < Cost[Cur].size(); i++)
            {
                int nDistance = Cost[Cur][i].second;
                int Next = Cost[Cur][i].first;
                if (Visit[Next] == false) PQ.push(make_pair(-nDistance, Next));
            }
        }
    }
}

line3 ~ 10)

- Priority_Queue를 선언 후, 임의의 정점을 선택해서(무난하게 역시나 1번 정점 선택) 해당 정점과 연결되어 있는

  간선들을 모두 Priority_Queue에 넣어준다.

  이 때, 값을 -Distance로 넣어주는데, 위의 코드와 같이 일반적으로 Priority_Queue<pair<int, int>> 로 선언할 경우

  내부에서는 "값이 클 수록 우선순위가 높다" 라고 판단하여서, 더 큰 값일수록 앞에 오도록(선입선출) 세팅된다.

  즉, 1번정점과 연결된 간선들의 길이가 { 2, 3, 5 } 라고 했을 때, MST를 만들어야 하는 우리 입장에서는 '2'를 가장

  우선적으로 선택해야 하는데, 저렇게 선언할 경우 { 5, 3, 2 } 순으로 우선순위를 가지게 된다.

  따라서 값을 음수로 바꿔줌으로써 크기를 바꿔줘 버리는 것이다.

  다시 그 값을 빼서 계산할 때에는 - 값을 붙여서 계산을 해주면 된다.

  이렇게 하지 않고, Priority_Queue 자체를 다음과 같이 선언하면 값이 작을 수록 높은 우선순위를 갖게된다.

priority_queue <int, vector<int>, greater<int> >  PQ;

line12)

- 1번 정점을 선택했다고 표시해준다.

line13 ~ 30)

- 전체적인 로직이 위에서 말했던 Dist[]배열을 사용할 때와 굉장히 비슷하다.

  Priority_Queue에서 값을 하나씩 빼면서(현재 Queue에 들어 있는 간선들 중, 최단 길이의 간선이 나오게 된다)

  해당 정점을 선택하고, 해당 정점을 선택함으로써 연결되는 정점들을

  Priority_Queue에 넣어 가면서 반복하는 과정이다.

 

이렇게 지금까지 프림 알고리즘을 구현하는 2가지 방법에 대해서 알아보았다.

본인도 혼자서 공부를 하고 이해한대로 써내려 가다보니 설명이 서툰부분도, 부족한 점도 있을 수 있는데 최대한 본인이

이해한대로 쉽게 풀어써 보았다.

그 과정에서 다른 많은 분들의 프림 알고리즘에 대해서도 보게 되었는데, 사람마다 개개인의 구현하는 방법에 있어서

차이가 조금은 있으니 위의 글은 언제까지나 약간의 참고용으로만 쓰고 위의 글 만이 정답이다 라고는 생각하지 않았으면

좋겠다.