최소 신장 트리 (MST)

최소 신장 트리(Minimum Spanning Tree)를 이해하기 위해선 신장 트리에 대해서 알아야 한다.

 

신장 트리 (Spanning Tree)

그래프의 모든 정점이 이어져 있지만 사이클이 없을 때 신장 트리(스패닝 트리)라고 한다. 이름처럼 트리이기 때문에 순환관계 없이 최소한의 간선으로 연결되어 있다. 정점이 $n$개라면 $n-1$개의 간선으로 모두 이을 수 있다.

 

최소 신장 트리 (MST)

스패닝 트리 중 간선의 가중치 합이 가장 작은 트리이다. MST를 구하는 알고리즘은 대표적으로 크루스칼(Kruskal), 프림(Prim)알고리즘이 있다.

 

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

순환이 생기지 않는 선에서 최대한 가중치가 작은 간선을 위주로 선택하는 알고리즘이다. 

1. 간선들을 가중치가 작은 순서대로 정렬한다
2. 가장 앞의 간선을 선택하고 순환이 생기지 않는지 체크한다. 순환이 생기지 않았다면 선택하고 생겼다면 버린다.
3. 위의 과정을 $n-1$개의 간선이 선택될 때까지 반복한다.

작동 원리는 굉장히 간단하다. 그렇다면 어떻게 순환이 생기는지 검사할 수 있을까? 바로 분리 집합(Disjoint Set)을 사용하면 된다. Union-Find를 통한 분리 집합 구현으로 같은 그룹에 속해 있는지(순환이 발생하는지) 확인할 수 있다.

 

예제

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

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

using namespace std;

int parent[10001];

int find(int x) {
    if (parent[x] == x)
        return x;
    else
        return parent[x] = find(parent[x]);
}

void uni(int x, int y) {
    x = find(x);
    y = find(y);
    parent[y] = x;
}

bool isFamily(int x, int y) {
    return find(x) == find(y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int v, e;
    cin >> v >> e;

    int result = 0;
    vector<tuple<int, int, int>> graph;

    for (int i = 0; i < e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph.emplace_back(c, a, b);
    }
    sort(graph.begin(), graph.end());

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

    for (int i = 0; i < graph.size(); i++) {
        int a, b, c;
        tie(c, a, b) = graph[i];
        if (!isFamily(a, b)) {
            uni(a, b);
            result += c;
        }
    }

    cout << result;
}