[MST - 2] Kruskal Algorithm

MST를 알아보았고, 이번에는 MST를 구하는 첫 번째 알고리즘인 Krustal Algorithm에 대해서 알아봅시다.

저번 포스트(MST - 1)에서 MST에서 사용되는 여러 용어들에 대해서 알아보았는데, Krustal Algorithm에서는

safe edge에 대한 개념이 사용됩니다.

기본적으로 Krustal Algorithm은 Find, Union의 구동 방식을 찾는데, 이에 대해서 먼저 알아봅시다.

---

find : Vertex(정점)의 집합인 Cut의 대표값이 다른지 검색하는 단계

union : 대표값이 다른 Cut 두 개를 합치는 단계

---

그림으로 보니까 이해가 되시나요?? Krustal Algorithm은 이게 전부입니다. 조금 유식하게 Krustal Algorithm을 표현해보면~

safe edge에 대한 두 Cut에 대해서, 이 두 Cut의 대표값이 다르면 합치면서 MST를 구하는 Algorithm

여기서 대표값이라는 것은 설정하기 나름입니다.ㅎㅎ 그러면 Krustal Algorithm에서 safe edge를 검색하는 방법은!?!?

간단해요. weight가 작은 순서대로 찾습니다..ㅋㅋㅋ 겁나 간단..

자 그럼 예시로 Algorithm의 동작을 알아봅시다.

---

이런 graph를 사용해보겠습니다. 대표값은 색으로 표시했습니다.ㅎㅎ 먼저 Krustal Algorithm은 가장 작은 weight 값부터 찾는다고 했으니까 값이 가장 작은 vertex인 (2,4)에 대해 먼저 동작 하겠네요!

아! 두 edge는 대표값이 달랐기 때문에 union됬네요!!! 전 공부할 때 vertex(정점) 번호가 작은 친구의 대표값으로 설정하도록 하였어요. 

다음은 (0,1) , (0,3)이 weight=3으로 동일하네요!! 이 두개 edge(간선)에 대한 연산이 종료하면 어떻게 될까요~??

오호~~ 이해가 되시나요~?? 어렵지 않은 방식이라 이해 되리라 믿습니다ㅎㅎ 그럼 계속 쭉 가볼까요!

step#4 (u,v) = (1,4) / weight = 4

자 여기서 봅시다. 그 다음 비교할 weight인 5, 7에 대한 edge를 보면 (3,4) / (1,3) 이죠. 그런데 아까 Find가 하는 역할이 어떤거였나요?

Vertex 2개의 대표값이 다른지 체크

지금 1, 3, 4 vertex(정점)의 대표값은 주황색으로 동일합니다. 그렇기에? 이 경우는 비교하지 않고 넘어가겠네요!

step#5 (u,v) = (2,5) / weight = 9

이렇게 알고리즘 동작이 마무리되고, 6개 vertex(정점) 모두 같은 대표값을 가지는 것, MST가 생성된 것을 알 수 있네요. 이 경우는 직접 손으로 해보면 더 이해가 빠르니까 해보는 것을 추천합니다!!!

이번엔 코딩은 어떻게 하련지 봅시다!

---

위 예시에서 봤던graph를 변수로 저장한 것들을 봅시다! 아 참고로 C++을 사용하였습니다~~!!

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 KrustalMST[6][6] = {0,};
int represent[6] = {0, 1, 2, 3, 4, 5}; // initial represent

typedef struct vertex{
    int u;
    int v;
    int weight;
}Vertex;
Vertex vertexs[10];
int vertexAmount = 0;

map은 graph가 되겠고, KrustalMST는 결과 저장, represent가 대표값이 되겠습니다. 그리고 구조체는 보면 알겠죠??ㅎㅎㅎㅎ 그 다음은 이제 find, union함수보다 main함수 먼저 보겠습니다.

int main()
{
    for(int i=0; i<6; i++)
    {
        for(int j=i; j<6; j++)
        {
            if(map[i][j] != 0)
            {
                vertexs[vertexAmount].u = i;
                vertexs[vertexAmount].v = j;
                vertexs[vertexAmount].weight = map[i][j];
                vertexAmount+=1;
            }
        }
    }
    sort(vertexs,vertexs+vertexAmount,WeightCompare);

    for(int i=0; i<vertexAmount; i++)
    {
        int U = vertexs[i].u;
        int V = vertexs[i].v;
        
        if(Find(U) != Find(V))
            Union(vertexs[i]);
        if(LoopEnd()) break;
    }
    
    cout<<"--------MST--------"<<endl;
    for(int i=0; i<6; i++)
    {
        for(int j=0; j<6; j++)
        {
            printf("%3d", KrustalMST[i][j]);
        }
        cout<<endl;
    }
    cout<<endl;
    return 0;
}

조금 하드 코딩을 해보았습니다..하하하..!!! 지금 각 vertex정보들을 저장하고, 오름차순으로 sort를 사용하였어요. STL의 함수입니다. STL의 유용한 기능들을 한번 정리해보는 포스트도 준비 해봐야겠네요ㅎㅎㅎ 지금 for loop부분이 핵심입니다. edge u, v에 대해서 대표값이 다르면 합치는 부분이에요. 알고리즘을 이해하고 계시다면 코드도 충분히 이해되실 겁니다.

int Find(int edge){ return represent[edge]; }
void Union(Vertex vertex)
{
    int representV = represent[vertex.v];
    int representU = represent[vertex.u];
    for(int i=0; i<6; i++)
    {
        if(represent[i]==representV) represent[i] = representU;
    }
    KrustalMST[vertex.u][vertex.v] = vertex.weight;
    KrustalMST[vertex.v][vertex.u] = vertex.weight;
}

Find, Union함수는 이러합니다. Find는 간단하게 대표값을 return하고, Union의 경우 vertex에 대해서 합치는 과정을 볼 수 있네요. 대표값을 바꾸는데 일괄 변경하는 모습이고, 결과 graph에 MST를 저장!!!  

이름은 겁나게 어려워 보이는데 이게 전부입니다.ㅋㅋㅋㅋ 이렇게 마무리하겠고, full code는 아래 url입니다!! 피드백이 있다면 바로바로 수용하겠습니다~!! ㅂㅂ~~ 

https://github.com/dinoHee/Krustal-Algorithm