[C/C++] 실전 알고리즘 강좌 19강. 크루스칼 알고리즘(Kruskal Algorithm)

학습 내용

---

크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘으로 흔히 여러 개의 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 할 때 최소 비용을 계산하기 위해 실제로 적용되는 알고리즘이다.

 

우선 그래프 이론을 위한 용어를 정리하면 다음과 같다.

노드 = 정점 = 도시: 그래프에서 동그라미에 해당되는 부분이다.
간선 = 거리 = 비용: 그래프에서 선에 해당하는 부분이다.

 

아래의 그래프를 살펴보았을 때 노드의 개수는 7개이고, 간선의 개수는 11개이다.

https://www.techiedelight.com/kruskals-algorithm-for-finding-minimum-spanning-tree/

 

이때 단 6개의 간선으로 모든 노드를 연결할 수 있다.

https://www.techiedelight.com/kruskals-algorithm-for-finding-minimum-spanning-tree/

 

또한 최소 비용 신장 트리를 만들 때 사용되는 간선의 개수는 항상 전체 노드 개수에서 1을 뺀 값이다.

 

크루스칼 알고리즘의 핵심 개념은 '간선을 거리가 짧은 순서대로 그래프에 포함시키면 어떨까?'이다. 먼저 모든 노드를 최대한 적은 비용으로 '연결만' 시키면 되기 때문에 모든 간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 차근차근 그래프에 포함시키면 되는 것이다. 단, 사이클을 형성하는 경우 간선을 포함하지 않는다. 여기서 사이클이란 말 그대로 그래프가 서로 연결되어 사이클을 형성하는 경우(원 혹은 closed form을 형성)를 뜻한다.

 

1. 정렬된 순서에 맞게 그래프에 포함시킨다.

2. 포함시키기 전에는 사이클 테이블을 확인한다.

3. 사이클을 형성하는 경우 간선을 포함하지 않는다.

 

위의 예제는 다음과 같이 동작한다.

 

사이클이 발생하는지의 여부는 Union-Find 알고리즘을 적용하면 된다. Union-Find로 만든 사이클 테이블을 이용하여 이미 같은 부모를 가지고 있는 경우에는 무시하고 넘어가도록 구현한다.

 

이를 코드로 나타내면 다음과 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 간선 클래스 선언
class Edge{
public:
    int node[2];
    int distance;
    Edge(int a, int b, int distance){
        this->node[0] = a;
        this->node[1] = b;
        this->distance = distance;
    }
    bool operator<(Edge &edge){
        return this->distance < edge.distance;
    }
};

// 부모 노드를 찾는 함수
int getParent(int parent[], int x){
    if(parent[x] == x) return x;
    return parent[x] = getParent(parent, parent[x]);
}

// 두 부모 노드를 합치는 함수
void unionParent(int parent[], int a, int b){
    a = getParent(parent, a);
    b = getParent(parent, b);
    if(a < b) parent[b] = a;
    else parent[a] = b;
}

// 같은 부모를 가지는지 확인
int findParent(int parent[], int a, int b){
    a = getParent(parent, a);
    b = getParent(parent, b);
    if(a == b) return 1;
    else return 0;
}

int main()
{
    int n = 7;
    int m = 11;
    
    vector<Edge> v;
    v.push_back(Edge(0, 1, 7));
    v.push_back(Edge(0, 3, 5));    
    v.push_back(Edge(1, 3, 9));
    v.push_back(Edge(1, 2, 8));
    v.push_back(Edge(1, 4, 7));
    v.push_back(Edge(2, 4, 5));
    v.push_back(Edge(3, 4, 15));
    v.push_back(Edge(3, 5, 6));
    v.push_back(Edge(4, 5, 8));
    v.push_back(Edge(4, 6, 9));
    v.push_back(Edge(5, 6, 11));
    
    // 간선의 비용을 기준으로 오름차순 정렬
    sort(v.begin(), v.end());
    
    // 각 정점이 포함된 그래프가 어디인지 저장
    int parent[n];
    for(int i = 0; i < n; i++){
        parent[i] = i;
    }
    
    int sum = 0;
    for(int i = 0; i < v.size(); i++){
        // 사이클이 발생하지 않는 경우 그래프에 포함
        if(!findParent(parent, v[i].node[0], v[i].node[1])){
            sum += v[i].distance;
            unionParent(parent, v[i].node[0], v[i].node[1]);
        }
    }
    
    cout << sum << endl;
    return 0;
}

 

크루스칼 알고리즘의 시간 복잡도는 정렬 알고리즘과 동일하다.