10-4. [C/C++] MST를 위한 Kruskal 알고리즘

Kruskal 알고리즘

Kruskal 알고리즘은 탐욕법(Greedy Algorithm, 이하 그리디)이라는 기법을 사용한다.

 

그리디 알고리즘은 어떤 결정을 해야 할 때마다 "그 순간에 최적"이라고 판단되는 것을 선택하는 방법이다.

물론 순간 최적의 선택이 궁극적으로 최적의 결과를 이끌어 낸다는 보장은 없다.

따라서 그리디 알고리즘은 항상 최적의 해답을 주는지 검증해야 한다.

하지만, Kruskal 알고리즘은 최적의 결과를 보장한다는 것이 증명되었다.

 

Kruskal 알고리즘은 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다.

위 과정을 반복해 그래프의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구한다.

Kruskal()

(1) 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
(2) 가장 가중치가 작은 간선 e를 선택한다.
(3) e를 신장 트리에 넣을 경우 사이클이 생기면 삽입하지 않고 2번으로 이동한다.
(4) 사이클이 생기지 않으면 최소 신장 트리에 삽입한다.
(5) n-1개의 간선이 삽입될 때 까지 2번으로 이동한다.

위 그림을 보며 알고리즘을 따라가다 보면 Kruskal 알고리즘의 과정은 쉽게 이해할 수 있을 것이다.

 

하지만, 알고리즘을 구현하기 위해 해결해야 할 것이 있다. 사이클이 생기는지를 검사하는 부분이다.

이미 선택된 간선들의 집합에 새로운 간선을 추가할 때 사이클이 생성되는지 검사해야 한다.

새로운 간선이 이미 다른 경로에 의해 연결되어 있는 정점들을 연결하면 사이클이 만들어진다.

반면, 간선이 서로 다른 집합에 속한 정점을 연결하는 경우 사이클이 만들어지지 않는다.

---

사이클 검사

그러면 사이클을 검사하는 방법을 알아보자.

초기에는 모든 정점을 각각의 집합에 위치 시킨다.

for (int i = 1; i <= V; i++)
	parent[i] = i;

parent[i] 는 i 번 정점이 속한 집합의 대표 정점이 i 라는 의미이다.

 

간선을 선택할 때 해당 간선에 해당하는 두 정점이 같은 집합에 있는 지 확인한다.

bool unionParent(int v1, int v2) {
	int u = findParent(v1);
    int v = findParent(v2);
    
    if (u == v) return false;
    ...
}

만약 같은 집합에 있는 정점을 잇는 간선인 경우 false를 반환해 간선을 MST에 추가하지 않도록 한다.

 

같은 집합에 있는 정점이 아닌 경우, 두 정점을 같은 집합으로 만든 뒤 true를 반환해 간선을 MST에 추가하도록 한다.

bool unionParent(int v1, int v2) {
	...
    else {
    	parent[u] = v;
        return true;
    }
}

---

코드로 구현

1197번: 최소 스패닝 트리

이 문제를 Kruskal 알고리즘을 이용해 해결해 봤다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
#define SIZE 10001

int V, E;
int parent[SIZE];
vector<tuple<int, int, int>> graph;
bool visited[SIZE];
long long ans;

int findParent(int u) {
    if (parent[u] == u) return u;
    return parent[u] = findParent(parent[u]);
}

bool unionParent(int v1, int v2) {
    int u = findParent(v1);
    int v = findParent(v2);

    if (u == v) return false;
    else {
        parent[u] = v;
        return true;
    }
}

void kruskal() {
    for (int i = 0; i < E; i++) {
        if (unionParent(get<1>(graph[i]), get<2>(graph[i])))
            ans += get<0>(graph[i]);
    }
}

int main() {
    cin >> V >> E;
    for (int i = 1; i <= V; i++) parent[i] = i;
    for (int i = 0; i < E; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;
        graph.push_back({weight, u, v});
    }
    sort(graph.begin(), graph.end());

    kruskal();
    cout << ans << endl;
    
    return 0;
}

위 코드는 아래 이미지를 클릭해 깃허브에서도 확인할 수 있다.