신장 트리와 Prim·Kruskal

여러 건물을 통신선으로 모두 이으려 할 때, 건물 사이마다 선을 깔 필요는 없습니다. 모든 건물이 어떤 길로든 이어지기만 하면 되므로, 사이클이 생기는 선은 하나를 빼도 연결이 유지됩니다. 그래서 가장 싸게 모두 잇는 방법은 언제나 트리 모양이 됩니다. 이 글에서는 트리와 이진 트리의 구조의 트리와 최단 경로와 단계별 갱신의 가중치 그래프를 이어, 모든 정점을 가장 적은 비용으로 잇는 트리를 찾습니다.

신장 트리와 최소 신장 트리

그래프에서 정점의 일부나 전부와, 고른 정점끼리 잇는 간선의 일부나 전부를 골라 만든 그래프를 부분 그래프(subgraph)라고 합니다. 연결된 무방향 그래프에서 모든 정점을 포함하면서 트리인 부분 그래프를 신장 트리(spanning tree)라고 합니다. 연결 그래프에는 언제나 신장 트리가 있습니다. 사이클이 남아 있는 동안 사이클 위의 간선을 하나씩 지우면 연결은 유지되고, 사이클이 없어지면 트리가 남기 때문입니다. 정점이 n개이면 신장 트리의 간선은 n − 1개입니다.

간선에 가중치가 있을 때 신장 트리 가운데 간선 가중치의 합이 가장 작은 것을 최소 신장 트리(minimum spanning tree, MST)라고 합니다. 가중치가 같은 간선이 있으면 합이 같은 최소 신장 트리가 여러 개일 수 있습니다. 그래프가 연결되어 있지 않으면 신장 트리가 없고, 연결 성분마다 최소 신장 트리를 구한 최소 신장 숲을 생각할 수 있습니다.

최소 신장 트리는 최단 경로와 목표가 다릅니다. 삼각형 AB = 2, BC = 2, AC = 3에서 최소 신장 트리는 AB와 BC로 합이 4입니다. 하지만 A에서 C로 가는 최단 경로는 간선 AC 하나로 비용이 3이고, 최소 신장 트리 안에서 A에서 C로 가면 4가 듭니다. 이것은 최소 신장 트리가 틀렸다는 뜻이 아닙니다. 최소 신장 트리는 전체를 잇는 비용의 합을 줄이고, 최단 경로는 두 정점 사이의 비용을 줄이기 때문입니다.

자르기 성질

최소 신장 트리를 찾는 알고리즘들은 모두 같은 성질을 씁니다. 정점 집합을 두 부분 S와 나머지로 나누는 것을 자르기(cut)라 하고, 양쪽을 잇는 간선을 그 자르기를 건너는 간선이라고 합니다. 자르기 성질(cut property)은 어떤 자르기를 건너는 간선 가운데 가중치가 가장 작은 간선 e가 어떤 최소 신장 트리에 들어 있다는 것입니다.

증명은 교환 논증(exchange argument)으로 합니다. 최소 신장 트리 T에 e가 없다고 합시다. T에 e를 더하면 e를 지나는 사이클이 하나 생기는데, e는 자르기의 양쪽을 이으므로 이 사이클은 반대 방향으로 자르기를 다시 건너는 간선 f를 하나 더 가지고 있습니다. T에 e를 더하고 f를 빼면 사이클이 끊겨 다시 신장 트리가 됩니다. e는 자르기를 건너는 간선 가운데 가장 가벼우므로 $w(e)\le w(f)$이고, 새 트리의 합은 T의 합보다 크지 않습니다. T가 최소였으므로 새 트리도 최소 신장 트리이고, 여기에는 e가 들어 있습니다.

알고리즘에서 이 성질을 여러 번 쓰려면 한 가지를 더 확인해야 합니다. 지금까지 고른 간선이 모두 최소 신장 트리 T에 들어 있고 그 가운데 자르기를 건너는 간선이 없다면, 자르기를 건너는 f는 고른 간선이 아니므로 e를 더하고 f를 뺀 새 트리에도 고른 간선이 모두 남습니다. 그래서 고른 간선이 건너지 않는 자르기에서 가장 가벼운 간선을 더해도, 고른 간선 전체가 하나의 최소 신장 트리에 들어 있다는 사실이 계속 유지됩니다.

같은 방법으로 반대쪽 성질도 보일 수 있습니다. 어떤 사이클에서 가중치가 엄격하게 가장 큰 간선은 어떤 최소 신장 트리에도 들어 있지 않습니다. 그 간선이 트리에 있다면 빼고 사이클의 다른 간선 하나를 넣어 합을 줄일 수 있기 때문입니다.

더 깊이: 가중치가 모두 다르면 최소 신장 트리는 하나뿐이다

같은 교환 논증으로, 연결 그래프의 간선 가중치가 모두 서로 다르면 최소 신장 트리가 하나뿐이라는 것도 보일 수 있습니다. 서로 다른 최소 신장 트리 $T_1$과 $T_2$가 있다고 가정하고, 둘 가운데 한쪽에만 있는 간선들 중 가장 가벼운 것을 e라 합니다. 이름을 바꾸어 e가 $T_1$에만 있다고 해도 됩니다.

$T_2$에 e를 더하면 사이클이 하나 생깁니다. $T_1$은 사이클이 없으므로 이 사이클의 간선이 모두 $T_1$에 있을 수는 없고, $T_1$에 없는 간선 f가 사이클에 적어도 하나 있습니다. f는 $T_2$에만 있는 간선이므로 e를 고른 방식에 따라 e보다 가볍지 않고, 가중치가 모두 다르니 $w(f)>w(e)$입니다. 그러면 $T_2$에 e를 더하고 f를 뺀 신장 트리의 합이 $T_2$보다 작아져, $T_2$가 최소라는 가정과 어긋납니다.

가중치가 같은 간선이 있으면 연습 문제 3처럼 최소 신장 트리가 여러 개일 수 있지만, 그 합은 언제나 같습니다. 가중치가 같은 간선 사이에 정해진 순서, 예를 들어 간선 번호를 덧붙여 비교하면 모든 가중치가 다른 경우로 바꿀 수 있어서, Prim과 Kruskal이 어느 간선을 먼저 고르든 같은 트리를 내게 만들 수 있습니다.

Prim은 트리 하나를 키우고, Kruskal은 조각을 합친다

Prim 알고리즘은 정점 하나에서 시작해 트리를 키웁니다. 지금 트리에 들어 있는 정점들을 S로 하는 자르기를 생각하고, 그 자르기를 건너는 간선 가운데 가장 가벼운 것을 골라 트리에 더하는 일을 모든 정점이 들어올 때까지 반복합니다. 지금까지 고른 간선은 모두 S 안에 있어 이 자르기를 건너지 않으므로, 자르기 성질에 따라 고른 간선 전체가 언제나 하나의 최소 신장 트리에 들어 있습니다. 간선 AB = 1, AC = 4, BC = 2, BD = 5, CD = 3인 그래프에서 A로 시작하면 AB = 1, BC = 2, CD = 3을 차례로 더해 합 6을 얻습니다. 비교하는 것이 출발점에서의 누적 거리가 아니라 간선 하나의 가중치라는 점이 Dijkstra 알고리즘과 다릅니다.

Kruskal 알고리즘은 모든 간선을 가중치가 작은 순서로 살펴보며, 서로 다른 조각을 잇는 간선이면 고르고 같은 조각 안의 두 정점을 잇는 간선이면 버립니다. 여기서 조각은 정점은 모두 두고 간선은 지금까지 고른 것만 남긴 그래프의 연결 성분입니다. 처음에는 고른 간선이 없으므로 정점 하나하나가 조각이고, 간선을 고를 때마다 두 조각이 하나로 합쳐집니다. 같은 조각 안을 잇는 간선은 사이클을 만들기 때문에 버리는 것입니다. 지금까지 고른 간선은 모두 조각 안에 있어 자기 조각과 나머지를 나누는 자르기를 건너지 않고, 이번에 고른 간선은 그 자르기를 건너는 가장 가벼운 간선이므로 자르기 성질에 따라 고른 간선 전체가 계속 하나의 최소 신장 트리에 들어 있습니다. 예제에서는 1(AB), 2(BC), 3(CD)을 고르면 조각이 하나가 되고, 4(AC)와 5(BD)는 같은 조각 안을 이으므로 버립니다.

from heapq import heappop, heappush


def kruskal(vertices, edges):
    parent = {v: v for v in vertices}

    def find(v):
        while parent[v] != v:
            parent[v] = parent[parent[v]]
            v = parent[v]
        return v

    chosen = []
    for weight, a, b in sorted(edges):
        root_a, root_b = find(a), find(b)
        if root_a != root_b:
            parent[root_a] = root_b
            chosen.append((weight, a, b))
    return chosen


def prim(vertices, edges, start):
    neighbors = {v: [] for v in vertices}
    for weight, a, b in edges:
        neighbors[a].append((weight, a, b))
        neighbors[b].append((weight, b, a))
    in_tree, chosen, heap = {start}, [], []
    for edge in neighbors[start]:
        heappush(heap, edge)
    while heap:
        weight, a, b = heappop(heap)
        if b in in_tree:
            continue
        in_tree.add(b)
        chosen.append((weight, a, b))
        for edge in neighbors[b]:
            if edge[2] not in in_tree:
                heappush(heap, edge)
    return chosen


edges = [(1, "A", "B"), (4, "A", "C"), (2, "B", "C"), (5, "B", "D"), (3, "C", "D")]
for tree in (kruskal("ABCD", edges), prim("ABCD", edges, "D")):
    print(tree, sum(weight for weight, _, _ in tree))

[(1, 'A', 'B'), (2, 'B', 'C'), (3, 'C', 'D')] 6
[(3, 'D', 'C'), (2, 'C', 'B'), (1, 'B', 'A')] 6

간선은 (가중치, 끝점, 끝점) 튜플이라서 sorted가 가중치 순서로 정렬하고, 힙도 가중치가 가장 작은 간선을 먼저 꺼냅니다. kruskal의 parent는 정점마다 같은 조각의 다른 정점을 가리키며, 끝까지 따라가 닿는 루트가 그 조각의 대표입니다. 두 정점의 대표가 같으면 같은 조각이고, 다르면 한쪽 대표가 다른 쪽을 가리키게 해서 조각을 합칩니다. 이런 구조를 서로소 집합(disjoint set) 또는 유니온-파인드(union-find)라고 하는데, 조각들은 "이어져 있다"는 동치관계의 동치류이므로 이 구조는 집합의 분할을 저장하는 셈입니다. find의 parent[v] = parent[parent[v]]는 지나가는 정점이 한 칸 위를 건너뛰어 가리키게 해서 다음 탐색을 빠르게 합니다.

prim은 D에서 시작했으므로 CD, BC, AB 순서로 간선을 더했지만, 결과는 Kruskal과 같은 트리입니다. 힙에서 꺼낸 간선의 끝이 이미 트리에 있으면 사이클을 만드는 간선이므로 건너뜁니다. 두 함수 모두 입력이 연결 그래프라고 가정합니다. 연결되어 있지 않으면 kruskal은 최소 신장 숲을, prim은 시작 정점이 속한 성분의 트리만 돌려주므로, 고른 간선이 n − 1개인지 확인해야 합니다.

정리

• 신장 트리는 모든 정점을 포함하는 트리인 부분 그래프이고, 최소 신장 트리는 그 가운데 간선 가중치의 합이 가장 작은 것입니다. 최소 신장 트리는 여러 개일 수 있습니다.
• 최소 신장 트리는 전체를 잇는 비용을 줄이고, 최단 경로는 두 정점 사이의 비용을 줄이므로 서로 다른 답을 냅니다.
• 자르기를 건너는 가장 가벼운 간선은 어떤 최소 신장 트리에 들어 있으며, 이것은 간선을 맞바꾸는 교환 논증으로 증명합니다.
• Prim 알고리즘은 트리 하나를 키우며 트리 밖으로 나가는 가장 가벼운 간선을 더하고, Kruskal 알고리즘은 가벼운 간선부터 서로 다른 조각을 잇는 것만 고릅니다.
• Kruskal 알고리즘은 서로소 집합으로 두 정점이 같은 조각인지 판단합니다.

연습 문제

1. 들어갈 수 없는 간선

예제 그래프에서 간선 AC = 4를 포함하는 신장 트리는 최소 신장 트리가 될 수 없음을 보이세요.

2. 간선이 모자라는 결과

정점 5개를 입력했는데 Kruskal 알고리즘이 간선 3개를 골랐습니다. 최소 신장 트리를 얻었다고 할 수 있나요?

3. 최소 신장 트리가 여러 개인 경우

정사각형 A, B, C, D의 네 변 AB, BC, CD, DA의 가중치가 모두 1입니다. 최소 신장 트리는 몇 개인가요?

손으로 추적할 때는 간선을 고를 때마다 지금의 조각들이 어떻게 나뉘어 있는지 함께 적어 보세요. 다음 글인 선택 심화 허프만 코드와 접두어 없는 표현에서는, Prim과 Kruskal이 매번 지금 가장 가벼운 간선을 고른 것처럼 그때그때 가장 좋아 보이는 것을 고르는 탐욕법으로, 가장 작은 두 값을 먼저 합쳐 트리를 만듭니다.