[MST - 3] Prim Algorithm

다음으로 볼 알고리즘은 MST를 구하는 두 번째 알고리즘인 Prim Algorithm입니다.

일전에 MST랑 Krustal Algorithm 에 대해서 알아보았는데, 이번에는 다른 MST를 찾는 Algorithm입니다!!

Prim Algorithm의 특징은 이러합니다.

---

1. 어떠한 vertex로 시작해도 결과는 똑같다.
2. 방향성을 가진다.
3. BFS처럼 주변을 먼저 살핀다.

---

Krustal Algorithm은 Find, Union 구동 방식을 사용하지만, Prim Algorithm의 경우는 vertex의 주변 vertex를 탐색하는 방법으로 MST를 찾습니다.

Prim Algorithm의 핵심은 key값이 있다는 것인데, Krustal Algorithm의 대표값이랑 비슷하면서도 다른 사용 방법을 가지고 있습니다.

---

• Krustal Algorithm의 대표값 Cut 두개를 합치기 위한 기준값
• Prim Algorithm의 대표값 MST의 edge로 선택된 weight값으로 어떤 길이 더 짧은지 비교하기 위한 기준값

---

그러면 예시를 통해서 Prim Algorithm을 알아봅시다!

---

이번에 사용할 예시입니다!!

Prim Algorithm은 초기 key(대표)값으로 INF를 가지고 있고, priority queue를 사용합니다.

먼저 6개에 대한 초기 key값은 이러하겠죠.

{INF, INF, INF, INF, INF, INF}

위에서 설명했던 Prim Algorithm의 장점 중 하나는 어떤 vertex로 시작해도 결과가 똑같다는 것이었어요.

전 먼저 0번 vertex를 시작 vertex로 삼겠습니다. 여기서 Prim Algorithm의 첫 번째 step이 나오네요.

Prim Algorithm의 첫 번째 step start vertex의 key값을 0으로 만들기

먼저 방향성 얘기를 하자면, 현재 제 예시는 vertex번호가 작은 쪽으로 방향성을 가지고 있습니다.

Prim Algorithm의 구동방식은 간단합니다. 현재 기준이 되는 vertex에 대해서 연결된 vertex들을 비교하는 것입니다.

지금 기준이 된 0번 vertex와 연결되어 있는 vertex는 1, 3번 vertex가 되겠죠. 그럼 이에 대해서 key값과 비교하는 것입니다.

비교해서 만약 기존 key값보다 weight값이 더 작으면? key값이 대체되면서 해당 edge가 채택!

Prim Algorithm의 두 번째 step 연결된 vertex의 weight값과 각각의 key값과 비교

Prim Algorithm의 세 번째 step key값보다 연결 edge의 weight값이 더 작다면? 해당 edge를 MST에 저장, key값 재설정

그림을 보면 이해가 되시나요? 제가 최대한 말이 되게 설명을 하고있긴 한데..맞는지 모르겠네요..ㅋㅋㅋㅋㅋ 직접 손으로 해보는 것을 추천합니다 ㅠㅠ

지금 2, 3번째 step을 거쳐서 1, 3번 vertex의 key값이 수정되었네요. 그럼 현재 key값들은?

{0,3,INF,3,INF,INF}

여기서 이제 priority queue의 역할이 나옵니다.

priority queue는 queue내에서 오름 혹은 내림차순 정렬이 되어서 최대, 최솟값만 알 수 밖에 없는 queue를 의미합니다.

여기서 사용된 priority queue는 key값이 작은 것을 pop하는 역할을 가지고 있습니다. 아, 물론 사용 안 했던 vertex들 중에서요!!!

인접 vertex에 대한 탐색을 마치면 queue에서 pop을 해서 탐색 기준 vertex를 얻게 되죠. 현재는 1이 되겠네요.

그 후에 다시 연결된 vertex에 대해 탐색을 하게 되면??

위 사진은 vertex1에 대한 결과값인데, 1과 인접한 vertex는 0, 2, 3, 4로 하나하나 봅시다. (현재 key {0,3,INF,3,INF,INF})

---

• vertex 0 현재 key값 : 0, edge의 weight값 : 3 현재 key이 더 작음!
• vertex 2 현재 key값 : INF, edge의 weight값 : 10 현재 key이 더 큼! key값 교체!
• vertex 3 현재 key값 : 3, edge의 weight값 : 7 현재 key이 더 작음!
• vertex 2 현재 key값 : INF, edge의 weight값 : 4 현재 key이 더 큼! key값 교체!

---

이렇게 되서 위의 그림이 된 것입니다! 그 다음 vertex 3에 대해서는 바뀔 값이 없네요!! 현재까지의 key값들은 이러합니다.

{0,3,10,3,4,INF}

이제는 vertex 4에 대해 검색을 하겠네요!!!

---

• vertex 1 현재 key값 : 3, edge의 weight값 : 4 현재 key이 더 작음!
• vertex 2 현재 key값 : 10, edge의 weight값 : 1 현재 key이 더 큼! key값 교체!
• vertex 3 현재 key값 : 3, edge의 weight값 : 5 현재 key이 더 작음!
• vertex 5 현재 key값 : INF, edge의 weight값 : 5 현재 key이 더 큼! key값 교체!

---

이렇게 key는 {0,3,1,3,4,10}이 되었네요. 다음 vertex 2까지 탐색하고 마치면 이렇게 되겠네요.

미숙한 설명은 끝났습니다ㅠㅠ 이제 이 부분에 대해서 한번 코딩을 해봅시다!!

---

#define INF 100000000
int map[6][6] = {
     0, 3, 0, 3, 0, 0,
     3, 0,10, 7, 4, 0,
     0,10, 0, 0, 1, 9,
     3, 7, 0, 0, 5, 0,
     0, 4, 1, 5, 0,10,
     0, 0, 9, 0,10, 0
}; //map
int PrimMST[6][6] = {0,};
typedef struct key
{
    int u;      //key값을 준 edge의 u
    int v;      //key값을 준 edge의 v
    int weight; //key값
}Key;
bool visit[6] = {false,};
Key key[6] = {{INF,INF,INF},{INF,INF,INF},{INF,INF,INF},{INF,INF,INF},
              {INF,INF,INF},{INF,INF,INF}};

사용한 변수들에 대해서 봅시다. 나머지는 그렇다치고, key값에 대해서 구조체를 사용한 이유는, 이제 key값이 교체될 때, 해당 key값을 준 edge에 대해서 교체를 시켜줘야하기 때문에 edge정보까지 저장해두려고 구조체를 사용했습니다. 그 다음은 priority_queue인데, 이것때문에 엄청 고민했는데, STL에 있더라구요..ㅋㅋㅋㅋ

struct cmp{
    bool operator()(int a, int b){
        return key[a].weight > key[b].weight;
    }
};

priority_queue<int,vector<int>,cmp> priorityQueue;

priority queue도 STL의 sort처럼 정렬 기준을 설정해줄 수 있어요. 그런데 sort와 다른 점은 cmp라는 구조체에 operator()함수를 overloading한다는 점입니다. 이렇게 queue까지 만들었습니다.

key[1].u = 0; key[1].v = 0; key[1].weight = 0; visit[1] = true;
    
    for(int i=0; i<6; i++)
    {
        if(map[1][i]!=0)
        {
            priorityQueue.push(i);
            Prim(1,i);
        }
    }
    
    while(!priorityQueue.empty())
    {
        int targetVertex = priorityQueue.top();
        priorityQueue.pop(); visit[targetVertex] = true;
        
        for(int i=0; i<6; i++)
        {
            if(map[targetVertex][i]!=0)
            {
                if((key[i].weight > map[targetVertex][i]) && (visit[i] == false))
                {
                    if(visit[i]==false) priorityQueue.push(i);
                    Prim(targetVertex,i);
                }
            }
        }
    }

다음은 main부분이 되겠습니다. 시험해보고자 start vertex를 1로 뒀네요ㅎㅎ while문 전까지가 첫 번째 start vertex에 대한 Algorithm 적용 부분입니다. 

먼저 인접 vertex를 queue에 push하고 알고리즘을 진행하네요. 

 while문을 보면 visit을 사용하였는데, Prim Algorithm은 일방향으로 방향성이 존재해서 역순하지 말라고 지정해놨습니다. 

그래서 현재 key값과 weight를 비교해보고, 알고리즘을 진행. 

간단한 코드네요!! 전체 코드는 여기있습니다. https://github.com/dinoHee/MST_Algorithms 

미숙한 설명 답답하면 피드백 남겨주시기 바랍니다..ㅎㅎ 감사합니다~!!!