최소 신장 트리 - 서로소 집합 유니온을 이용한 Kruskal 알고리즘¶

MST 문제와 Kruskal 알고리즘에 대한 설명은 먼저 Kruskal 알고리즘 메인 문서를 참고하십시오.

이 문서에서는 Kruskal 알고리즘을 구현하기 위해 "서로소 집합 유니온" 자료 구조를 살펴봅니다. 이 자료 구조를 사용하면 알고리즘이 $O(M \log N)$의 시간 복잡도를 달성할 수 있습니다.

설명¶

단순한 버전의 Kruskal 알고리즘과 마찬가지로, 그래프의 모든 간선을 가중치의 비내림차순으로 정렬합니다. 그런 다음 make_set 함수를 호출하여 각 정점을 자기 자신만의 트리(즉, 자신의 집합)에 넣습니다. 이 과정에는 총 $O(N)$이 걸립니다. (정렬된 순서대로) 모든 간선을 순회하면서, 각 간선에 대해 두 끝점이 서로 다른 트리에 속하는지 판별합니다(각각 $O(1)$인 find_set 호출 두 번으로). 마지막으로 두 트리(집합)를 합쳐야 하며, 이를 위해 DSU의 union_sets 함수를 호출합니다. 이 역시 $O(1)$입니다. 따라서 전체 시간 복잡도는 $O(M \log N + N + M)$ = $O(M \log N)$입니다.

구현¶

다음은 랭크에 의한 합치기(Union by Rank)를 사용한 Kruskal 알고리즘의 구현입니다.

vector<int> parent, rank;

void make_set(int v) {
    parent[v] = v;
    rank[v] = 0;
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rank[a] < rank[b])
            swap(a, b);
        parent[b] = a;
        if (rank[a] == rank[b])
            rank[a]++;
    }
}

struct Edge {
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};

int n;
vector<Edge> edges;

int cost = 0;
vector<Edge> result;
parent.resize(n);
rank.resize(n);
for (int i = 0; i < n; i++)
    make_set(i);

sort(edges.begin(), edges.end());

for (Edge e : edges) {
    if (find_set(e.u) != find_set(e.v)) {
        cost += e.weight;
        result.push_back(e);
        union_sets(e.u, e.v);
    }
}

참고: MST는 정확히 $N-1$개의 간선을 포함하므로, 그만큼의 간선을 찾으면 for 루프를 멈출 수 있습니다.

연습 문제¶

이 주제에 관한 연습 문제 목록은 Kruskal 알고리즘 메인 문서를 참고하십시오.