[나만 몰랐던 알고리즘] MST 구하기 - Kruskal's Algorithm

Minimun Spanning Tree는 모든 노드를 잇는 사이클이 없는 그래프 중 간선(edge)의 가중치 합이 최소가 되는 트리(그래프)이다.

글로 봤을땐 저게 뭔가 싶은데 그림으로 한번 보자

위 사진과 같은 그래프에서, 모든 노드를 포함하는 부분 그래프를 신장 부분 그래프라고 한다. 여기서 간선이 어떻게 연결되는지에 따라 여러개의 신장 부분 그래프를 만들 수 있는데, 이 중 간선의 합이 최소가 되는 신장 부분 그래프를 MST라고 하고, 오늘 정리할 알고리즘은 이 MST를 찾는 Kruskal 알고리즘이다.

알고리즘을 크게 정리하면,

1. 모든 에지를 Cost 순으로 정렬되는 Priority Queue에 넣는다.
2. PQ에서 하나를 뽑는다 -> 이 에지의 출발점과 도착점이 연결되어 있지 않다면 트리에 추가한다. - Union-Find를 활용
3. 모든 에지가 연결되어있거나, 노드 수 - 1개의 에지를 뽑았으면 MST 완성!
4. PQ가 소진될때까지 다 돌았음에도 모두 연결이 되지 않는다면 해당 그래프는 MST가 없다!

Prim's Algorithm보다 이해하기 쉬워 MST 문제를 전부 이걸로 푼것 같다.

처음 보면 PQ다 Union-Find다 복잡한데, PQ는 STL에 구현되어 있는것을 활용하면 되고 Union-Find는 찬찬히 보면 쉽게 이해할 수 있다.

---

사전준비

typedef struct edge{
    int start;
    int end;
    int cost;
    edge(int start, int end, int cost): start(start), end(end), cost(cost) {}
} edge;

struct cmp{
    bool operator()(edge t, edge u) {
        return t.cost > u.cost;
    }
};

Priority Queue에서 사용할 에지 스트럭트와 비교 연산을 정의해준다. edge 구조체는 에지가 잇는 두 노드와 해당 에지의 비용을 저장한다. 물론 각각 배열을 만들어서 에지 인덱스로 접근하는 등의 방법이 있지만, PQ에도 넣어야 하고 이해하기가 직관적이라 따로 구조체를 생성해서 사용한다.

모든 에지를 PQ에 넣는다

std::priority_queue<edge, std::vector<edge>, cmp> pq;
int V, E;
std::cin >> V >> E;
int parent[V+1];
for (int i = 0; i <= V; i++){
    parent[i] = i;
}
for (int i = 0 ; i < E; i++){
    int S, F, C;
    std::cin >> S >> F >> C;
    pq.push(edge(S, F, C));
}

Priority queue를 생성하고 노드 수, 에지 수를 받아 초기화한다. Parent[]배열은 Union-Find에서 사용되는 각 노드 부모를 가르키는 배열이다. 이후 매 에지 연결 노드, 비용을 입력받다 pq에 push 한다.

Priority Queue 생성시 들어가는 인자는 <PQ에서 쓸 자료형, PQ내부에서 사용할 자료구조(컨테이너), PQ에서 각 원소를 비교할때 쓰는 연산> 이다.

PQ에서 하나씩 뽑으며 MST 생성

int cnt = 0;
int cost = 0;
while (!pq.empty()) {
    edge now = pq.top();
    pq.pop();
    if (cnt == V - 1)
        break;
    if (findParent(now.start, parent) == findParent(now.end, parent))
        continue;
    else {
        unionElement(now.start, now.end, parent);
        cnt++;
        cost += now.cost;
    }
}

에지 개수를 셀 변수와 MST의 비용을 셀 변수를 생성한다.

이후 PQ가 빌때까지 while을 돈다. 이 외에 사이클 없이 모든 노드가 최소 비용으로 연결된다면, 에지의 수는 N-1 이므로 포함한 에지가 노드 수 - 1일때도 루프를 탈출한다. 

루프에선 PQ에서 top을 구하고 뽑는다. 그 top원소는 PQ에서 cost가 가장 작은 에지이다. 해당 에지가 연결하는 두 노드가 같은 곳에 속하는지(부모가 같은지) 확인하면 두 노드가 연결되는지 확인 가능하다. - 여기서 Union-Find를 사용한다. 만약 두 노드가 같은 곳에 속한다면 해당 노드는 버리고 다시 에지를 뽑는다.

만약 두 노드가 같은곳에 속하지 않으면 해당 에지를 사용해 두 노드를 연결해주고(Union 해준다), 에지를 추가했으니 cost값을 1 증가시킨다.  문제에 따라 MST의 비용을 구하라 하면 cost 변수에 방금 넣은 에지의 cost를 합쳐준다.

 

해당 루프가 다 돌고 cost를 확인하면 MST의 비용을 확인할 수 있다.

문제에 따라 MST가 존재하지 않을수도 있다. 이때는 두가지 방법을 사용 가능하다.

 

첫번째로 추가한 에지의 수가 노드 - 1개인지 확인하는 방법. 나는 다른 문제에서 이런 접근을 했고, 쓸만 했다. 하지만 문제에 따라 cnt가 다르게 연산되는 경우도 있을 수 있다.

두번째로 parents[] 배열을 보고 모두 같은 값을 가지는지 확인하는 방법. 하나라도 다른 값을 가지면 모두 연결되지 않았다는 의미이므로 MST가 없다는 결론을 낼 수 있다.

---

MST 이름만 봤을때는 이게 뭐시다냐 했는데, 차근차근 알고리즘을 보고 구현해보니 나쁘지 않은것 같다. 한줄한줄 이해하고 아! 하는게 나쁘지 않은것 같다... 이렇게 알고리즘의 세계로 빠지는건가...