최소 신장 트리 - Kruskal 알고리즘¶

가중치가 있는 무방향 그래프가 주어집니다. 이 그래프의 부분 그래프 중에서 모든 정점을 연결하고(즉, 신장 트리이고) 가능한 모든 신장 트리 가운데 가중치가 가장 작은(즉, 모든 간선의 가중치 합이 최소인) 서브트리를 찾고자 합니다. 이러한 신장 트리를 최소 신장 트리라고 합니다.

왼쪽 그림에서는 가중치가 있는 무방향 그래프를, 오른쪽 그림에서는 그에 대응하는 최소 신장 트리를 볼 수 있습니다.

무작위 그래프 이 그래프의 MST

이 글에서는 최소 신장 트리와 관련된 몇 가지 중요한 사실을 살펴본 다음, 최소 신장 트리를 찾는 Kruskal 알고리즘의 가장 간단한 구현을 제시합니다.

최소 신장 트리의 성질¶

모든 간선의 가중치가 서로 다르면 그래프의 최소 신장 트리는 유일합니다. 그렇지 않으면 최소 신장 트리가 여러 개 존재할 수 있습니다. (특정 알고리즘은 일반적으로 가능한 최소 신장 트리 중 하나를 출력합니다.)
모든 간선의 가중치가 양수이면, 최소 신장 트리는 간선 가중치의 곱이 최소인 트리이기도 합니다. (이는 모든 간선 가중치를 그 로그값으로 바꾸어 증명할 수 있으며, 이렇게 해도 간선 가중치의 순서는 유지됩니다.)
그래프의 최소 신장 트리에서 간선의 최대 가중치는 그 그래프의 가능한 모든 신장 트리 가운데 가장 작습니다. (이는 Kruskal 알고리즘의 정당성으로부터 따라 나옵니다.)
그래프의 최대 신장 트리(간선 가중치의 합이 최대인 신장 트리)는 모든 간선 가중치의 부호를 반대로 바꾼 다음 최소 신장 트리 알고리즘 중 아무것이나 적용하여, 최소 신장 트리와 비슷한 방식으로 구할 수 있습니다.

Kruskal 알고리즘¶

이 알고리즘은 1956년 Joseph Bernard Kruskal, Jr.가 기술하였습니다.

Kruskal 알고리즘은 처음에 원래 그래프의 모든 노드를 서로 고립된 상태로 두어 단일 노드 트리들로 이루어진 포레스트를 만들고, 이후 매 반복마다 전체 트리 중 임의의 두 트리를 원래 그래프의 어떤 간선으로 결합하면서 이 트리들을 점차 병합합니다. 알고리즘을 실행하기 전에 모든 간선을 가중치 기준으로 (비내림차순으로) 정렬합니다. 그런 다음 합치는 과정이 시작됩니다. 첫 번째 간선부터 마지막 간선까지 (정렬된 순서로) 모든 간선을 차례로 고르고, 현재 고른 간선의 양 끝이 서로 다른 서브트리에 속하면 두 서브트리를 합치고 그 간선을 답에 추가합니다. 그래프가 연결되어 있다면 모든 간선을 순회한 뒤 모든 정점이 같은 서브트리에 속하게 되며, 최소 신장 트리를 얻게 됩니다. 그래프가 연결되어 있지 않다면, 같은 과정을 거쳐 대신 최소 신장 포레스트를 얻습니다.

가장 간단한 구현¶

다음 코드는 위에서 설명한 알고리즘을 그대로 구현한 것이며, 시간 복잡도는 $O(M \log M + N^2)$입니다. 간선을 정렬하는 데에는 $O(M \log N)$($O(M \log M)$과 같습니다)번의 연산이 필요합니다. 각 정점이 속한 서브트리에 대한 정보는 배열 tree_id[]를 이용해 유지합니다. 각 정점 v에 대해 tree_id[v]는 v가 속한 트리의 번호를 저장합니다. 각 간선에 대해 양 끝점이 서로 다른 트리에 속하는지는 $O(1)$에 판별할 수 있습니다. 마지막으로, 두 트리의 합치기는 tree_id[] 배열을 한 번 단순히 훑는 방식으로 $O(N)$에 수행됩니다. 병합 연산의 총 횟수가 $N-1$이므로 $O(M \log N + N^2)$의 점근적 동작을 얻습니다.

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

int n;
vector<Edge> edges;

int cost = 0;
vector<int> tree_id(n);
vector<Edge> result;
for (int i = 0; i < n; i++)
    tree_id[i] = i;

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

for (Edge e : edges) {
    if (tree_id[e.u] != tree_id[e.v]) {
        cost += e.weight;
        result.push_back(e);

        int old_id = tree_id[e.u], new_id = tree_id[e.v];
        for (int i = 0; i < n; i++) {
            if (tree_id[i] == old_id)
                tree_id[i] = new_id;
        }
    }
}

정당성 증명¶

Kruskal 알고리즘이 올바른 결과를 내는 이유는 무엇입니까?

원래 그래프가 연결되어 있었다면 결과 그래프도 연결되어 있습니다. 그렇지 않다면 적어도 하나의 간선으로 연결될 수 있는 두 연결 요소가 존재할 것이기 때문입니다. 하지만 이는 불가능합니다. 두 연결 요소의 id가 서로 다르므로 Kruskal 알고리즘이 이 간선들 중 하나를 선택했을 것이기 때문입니다. 또한 알고리즘에서 사이클을 명시적으로 금지하므로 결과 그래프에는 사이클이 전혀 없습니다. 따라서 이 알고리즘은 신장 트리를 생성합니다.

그렇다면 이 알고리즘은 왜 최소 신장 트리를 만들어 내는 것입니까?

"$F$가 알고리즘의 임의의 단계에서 알고리즘이 선택한 간선들의 집합이라면, $F$의 모든 간선을 포함하는 MST가 존재한다"라는 명제를 귀납법으로 보일 수 있습니다.

처음에는 이 명제가 자명하게 참입니다. 공집합은 모든 MST의 부분집합이기 때문입니다.

이제 $F$가 알고리즘의 임의의 단계에서의 어떤 간선 집합이고, $T$가 $F$를 포함하는 MST이며, $e$가 Kruskal 알고리즘으로 새로 추가하려는 간선이라고 가정합시다.

$e$가 사이클을 만든다면 이를 추가하지 않으므로, 이 단계 이후에도 명제는 여전히 참입니다.

$T$가 이미 $e$를 포함하는 경우에도 이 단계 이후 명제는 참입니다.

$T$가 간선 $e$를 포함하지 않는 경우, $T + e$는 사이클 $C$를 포함하게 됩니다. 이 사이클은 $F$에 속하지 않는 간선 $f$를 적어도 하나 포함합니다. 간선 집합 $T - f + e$ 역시 신장 트리가 됩니다. $f$의 가중치는 $e$의 가중치보다 작을 수 없다는 점에 주목하십시오. 그렇지 않다면 Kruskal 알고리즘이 $f$를 더 먼저 선택했을 것이기 때문입니다. 또한 더 큰 가중치를 가질 수도 없습니다. 그렇게 되면 $T - f + e$의 총 가중치가 $T$의 총 가중치보다 작아지는데, $T$는 이미 MST이므로 이는 불가능하기 때문입니다. 즉, $e$의 가중치는 $f$의 가중치와 같아야 합니다. 따라서 $T - f + e$ 역시 MST이며, $F + e$의 모든 간선을 포함합니다. 그러므로 이 경우에도 이 단계 이후 명제는 여전히 성립합니다.

이로써 명제가 증명됩니다. 즉, 모든 간선을 순회한 후 얻어지는 간선 집합은 연결되어 있고 어떤 MST에 포함되므로, 그 자체로 이미 MST여야 합니다.

개선된 구현¶

서로소 집합 유니온 (DSU) 자료 구조를 사용하면 약 $O(M \log N)$의 시간 복잡도를 갖는 더 빠른 Kruskal 알고리즘 구현을 작성할 수 있습니다. 이 글에서 그러한 접근 방식을 자세히 설명합니다.