크루스칼 알고리즘

안전한 간선 보조정리를 사용하는 또 다른 방법은 모든 간선을 정렬한 뒤, 처음에 비어 있는 신장 트리에 가중치가 증가하는 순서대로 간선을 추가해 보는 것입니다.

다음 간선이 이미 연결된 두 정점을 연결한다면, 그 간선은 무시합시다. 그렇지 않다면 그 간선은 서로 다른 두 컴포넌트를 연결하는 간선 중 최소이므로 안전하며, 추가할 수 있습니다.

매우 간단하게 들립니다: 모든 간선을 정렬하고, 반복문으로 순회하면서 정점들이 서로 다른 컴포넌트에 있는지 확인하면 됩니다. 하지만 모든 간선의 끝점에서 dfs로 하는 단순한 확인은 $O(nm)$에 동작합니다. 확인에 서로소 집합을 사용하면 점근적 복잡도를 간선 정렬 비용인 $O(m \log m)$까지 개선할 수 있습니다.

DSU 구현을 제외하면 코드는 매우 짧습니다:

struct Edge {
    int from, to, weight;
};

vector<Edge> edges;

sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
    return a.weight < b.weight;
});

for (auto [a, b, w] : edges) {
    // компоненты разные, если лидеры разные
    if (p(a) != p(b)) {
        // добавим ребро (a, b)
        unite(a, b);
    }
}

신장 트리는 매트로이드의 특수한 경우이므로, 크루스칼 알고리즘은 라도-에드먼즈 알고리즘의 특수한 경우입니다.