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

크루스칼( Kruskal ) 알고리즘

Kruskal 알고리즘은 최소 신장 트리( Minimal Spanning Tree )를 구하는 알고리즘입니다.

 

먼저, 신장 트리( Spanning Tree )는 그래프에 있는 모든 노드를 지나는 트리를 말합니다.

 

주어진 그래프

 

 

신장 트리는 N개의 정점을 가진 그래프에서 순환 구조가 없는 N-1개의 간선을 선택해서 만들 수 있습니다.

위의 그래프에서는 다음과 같은 신장 트리를 찾을 수 있습니다.

( 아래의 예보다 더 많은 신장 트리가 있습니다 )

 

신장 트리( spanning tree )의 예

 

 

그리고, 최소 신장 트리( MST )는 여러 개의 신장 트리 중, 최소 거리( 가중치 )를 가진 신장 트리를 말합니다.

 

최소 신장 트리( Minimal Spanning Tree, MST )

 

위의 오른쪽 이미지가 가장 작은 가중치를 가진 신장 트리입니다.

 

이러한 최소 신장 트리를 구하는 알고리즘의 하나가 Kruskal 알고리즘입니다.

이 알고리즘은 탐욕( greedy ) 알고리즘에 속하는 알고리즘으로,

주어진 간선들 중에서, 최소의 가중치를 가진 간선을 우선 선택해 가면서 트리를 만드는 알고리즘입니다.

 

탐욕( greedy ) 알고리즘은 항상 최적의 답을 찾을 수 있는 것이 아닙니다.

그러나, Kruskal 알고리즘은 최적은 답을 찾을 수 있다는 것이 증명되었습니다.

 

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

 

1. 간선이 가진 가중치를 기준으로 오름차순으로 정렬
2. 가장 작은 가중치를 가진 간선을 선택.
3. 이 간선이 이전에 선택된 간선들과 순환 경로를 만들면, 트리에서 제거. 그렇지 않으면 신장 트리에 포함.
4. 2의 과정을 남은 간선을 대상으로 반복.

 

여기서, 주어진 간선이 순환 경로를 만드는지를 판단하기 위해서 Union-Find 알고리즘을 사용합니다.

Union-Find 알고리즘은 여기에 정리해 두었습니다.

[C++] 분리 집합( Disjoint Set )과 합집합 찾기( Union-Find ) 알고리즘

 

간선을 MST에 추가하기 전에, 간선의 두 정점이 같은 집합에 속하는지 검사를 합니다.

두 점정이 같은 집합에 속하지 않으면, 간선을 MST에 추가한 후, 두 정점이 속한 집합들을 결합합니다.

 

만약, 간선의 두 정점이 이미 같은 집합에 속해 있다면, 그 간선은 이전의 간선들과 함께 순환 경로를 만든다는 것을 알 수 있습니다.

 

이제, 다음과 같은 그래프가 주어졌을 때, 위의 Kruskal 알고리즘 과정을 적용해 보겠습니다.

 

가중치가 있는 그래프

 

먼저, 이 그래프 간선들의 가중치를 오름차순으로 정렬합니다.

1, 2, 5, 8, 10, 11, 12

 

가중치 1이 가장 작으므로 가중치 1을 갖는 간선을 선택합니다.

( 그러면서, 1번과 2번 정점을 같은 집합에 넣습니다 )

 

다음 작은 가중치는 2이므로, 가중치 2를 갖는 간선을 선택합니다.

( 3번과 4번을 같은 집합에 넣습니다 )

 

 

 

 

다음 가중치는 5이므로, 가중치 5를 갖는 간선을 선택합니다.

( 3번과 5번을 같은 집합에 넣습니다.)

 

그런데, 다음 가중치인 8을 가진 간선은 트리를 구성할 수 없습니다.

순환 경로를 만들기 때문입니다.

( 4번, 5번 정점이 이미 같은 집합에 속해 있습니다.)

따라서, 이 간선은 제외합니다.

 

 

 

 

다음 가중치는 10이므로, 가중치 10을 갖는 간선을 선택합니다.

그리고, 나머지 11, 12 가중치의 간선들은 모두 순환 경로를 만들므로, 트리 구성에 제외합니다.

 

 

 

 

이렇게 해서, 주어진 그래프로부터 최소 신장 트리를 만들었습니다.

 

최소 신장 트리( MST )

 

이 과정을 코드로 작성하면 다음과 같습니다.

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

#define VERT_SIZE   5
int parent[VERT_SIZE+1];

struct Edge{
    int s, e, w;

    Edge(int s, int e, int w){
        this->s = s;
        this->e = e;
        this->w = w;
    }
};

bool compare( const Edge& e1, const Edge& e2){
    return e1.w < e2.w;
}

// Union-Find
int Find_Root( int a){

    if ( parent[a] == a) 
        return a;

    return parent[a] = Find_Root( parent[a]);
}

// Union-Find
void Union( int a, int b){
    int ra = Find_Root(a);
    int rb = Find_Root(b);

    if ( ra != rb){
        parent[ra] = rb;
    }
}

int main(){

    vector<Edge> graph;
    graph.emplace_back(1, 2, 1);    // 간선 추가 ( 정점 s, e 가중치 w )
    graph.emplace_back(1, 3, 12);
    graph.emplace_back(2, 3, 10);
    graph.emplace_back(2, 4, 11);
    graph.emplace_back(3, 4, 2);
    graph.emplace_back(3, 5, 5);
    graph.emplace_back(4, 5, 8);

    for(int i = 0; i < VERT_SIZE+1; i++){   // 모든 정점을 집합으로 개별 집합으로 시작
        parent[i] = i;
    }

    sort( graph.begin(), graph.end(), compare); // 가중치를 오름차순으로 정렬

    int nTotalWeight = 0;

    for( const Edge& x : graph){
        
        // 간선의 정점이 같은 집합에 속하면, 순환 경로를 생성하기 때문에
        // 같은 집합이 아닌 경우 간선 추가
        if (Find_Root(x.s) != Find_Root(x.e)){
            
            nTotalWeight += x.w;    // MST에 간선 추가
            
            Union(x.s, x.e);
        }
    }

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

    return 0;
}

위 이미지의 그래프를 입력받아, 최소 신장 트리의 가중치 합을 출력하는 코드입니다.

Find_Root와 Union 함수에 대한 설명은 Union-Find 알고리즘에서 보실 수 있습니다.