최소 신장 트리

최소 신장 트리는 여러 지점을 가장 적은 비용으로 모두 이어 줍니다. 이을 수 있는 선들과 선마다의 비용을 넣으면 놓을 선들이 나옵니다. 어느 지점이든 다른 지점을 거쳐서 닿기만 하면 됩니다. 고리 속 구간 하나는 빼도 여전히 이어집니다. 그래서 가장 싼 답에는 빙 도는 고리가 하나도 없습니다.

상세

이 절은 최소 신장 트리 문제가 무엇을 받아 무엇을 내는지부터 봅니다. 그다음 건물 다섯 동짜리 작은 예 하나로 답을 직접 구해 봅니다. 답이 왜 맞는지, 얼마나 걸리는지, 헷갈리는 이웃과 무엇이 다른지는 그 뒤에 봅니다.

넣는 것과 나오는 것

최소 신장 트리 문제는 그래프 위에서 풉니다. 그래프는 점과 그 점들을 잇는 선으로 관계를 나타낸 구조입니다. 건물과 케이블 구간처럼 무엇과 무엇이 이어질 수 있는지를 담습니다.

점을 노드, 선을 간선이라고 부릅니다. 케이블 예라면 건물이 노드이고, 깔 수 있는 구간이 간선입니다. 노드를 정점이라고도 부릅니다.

간선마다 붙은 숫자가 가중치입니다. 그 간선을 쓰는 비용을 뜻합니다. 케이블 예라면 그 구간의 공사비가 가중치입니다.

간선에는 방향이 없습니다. 두 건물을 잇는 케이블은 어느 쪽에서 봐도 같은 케이블이기 때문입니다. 이런 그래프를 무방향 그래프라고 합니다.

그래프는 한 덩어리로 이어져 있어야 합니다. 어느 노드에서 출발해도 간선을 따라 다른 모든 노드에 닿을 수 있다는 뜻입니다. 이런 그래프를 연결 그래프라고 합니다.

정리하면 넣는 것은 가중치가 붙은 연결된 무방향 그래프 하나입니다. 나오는 것은 그 그래프의 간선 가운데 일부입니다. 어떤 간선을 고르는지는 다음 두 소절이 정합니다.

답이 트리가 되는 까닭

간선을 따라가다 출발한 노드로 되돌아오는 고리를 사이클이라고 합니다. 가에서 나, 나에서 다, 다에서 다시 가로 오는 길이 사이클입니다.

케이블 배선의 답에는 사이클이 없어야 합니다. 사이클이 있으면 그 고리에서 구간 하나를 빼도 건물들은 여전히 이어집니다. 뺀 구간의 공사비만큼 돈이 헛나간 셈입니다.

모든 노드가 이어져 있으면서 사이클이 없는 그래프를 트리라고 합니다. 노드가 V 개인 트리는 간선이 늘 V − 1 개입니다. 트리에서 간선 하나를 빼면 둘로 끊어집니다. 간선 하나를 더하면 사이클이 생깁니다.

원래 그래프의 노드를 모두 담으면서 간선은 일부만 골라 만든 트리를 신장 트리라고 합니다. 신장(spanning)은 모든 노드를 빠짐없이 덮는다는 뜻입니다. 한 그래프에는 신장 트리가 대개 여럿 있습니다.

신장 트리 가운데 가중치 합이 가장 작은 것이 최소 신장 트리입니다. 영어 이름 Minimum Spanning Tree 를 줄여 MST 라고도 씁니다.

모두 늘어놓으면 안 되는 까닭

신장 트리를 전부 늘어놓고 합을 비교해도 답은 나옵니다. 걸리는 것은 그 수입니다. 노드가 V 개이고 모든 노드 쌍 사이에 간선이 있으면 신장 트리는 V 의 V − 2 제곱 개입니다.

노드 열 개면 10 의 8 제곱, 곧 1억 개입니다. 노드 스무 개면 20 의 18 제곱이라 전부 볼 수가 없습니다. 그래서 늘어놓지 않고 간선을 하나씩 골라 답에 닿는 절차가 필요합니다.

예로 쓸 그래프

건물 가동 · 나동 · 다동 · 라동 · 마동 다섯 동과 깔 수 있는 구간 일곱 개입니다. 그림에는 동 이름의 첫 글자만 적었습니다. 선 위의 숫자가 공사비, 곧 가중치입니다.

flowchart TD
    A((가)) ---|4| B((나))
    A ---|1| C((다))
    B ---|3| C
    B ---|2| D((라))
    C ---|5| D
    C ---|6| E((마))
    D ---|7| E

노드가 다섯 개이므로 답은 간선 네 개짜리 트리입니다. 일곱 개 가운데 사이클이 안 생기게 네 개를 고르면 모두 신장 트리입니다. 그중 합이 가장 작은 것을 찾습니다.

싼 간선부터 넣어 보기

가장 손쉬운 방법은 싼 간선부터 차례로 넣어 보는 것입니다. 넣으려는 간선이 사이클을 만들면 버립니다. 간선이 V − 1 개가 되면 멈춥니다.

사이클이 생기는지는 조각으로 가립니다. 이미 넣은 간선으로 이어진 노드 묶음을 조각이라 부릅니다. 처음엔 노드 하나하나가 따로 조각입니다. 두 끝이 이미 같은 조각에 든 간선을 넣으면 사이클이 생깁니다.

아래 표는 예시 그래프의 간선을 가중치 순으로 늘어놓고 하나씩 판정한 것입니다. 표의 한 행이 간선 하나입니다.

4번과 5번은 두 끝이 이미 같은 조각에 들어 있어서 버렸습니다. 6번에서 간선이 네 개가 됐으므로 라–마(7) 은 볼 필요가 없습니다. 고른 간선의 가중치 합은 1 + 2 + 3 + 6 으로 12 입니다.

아래 그림은 같은 그래프에서 고른 간선을 실선으로, 버리거나 안 본 간선을 점선으로 그린 것입니다.

flowchart TD
    A((가)) -.-|4| B((나))
    A ---|1| C((다))
    B ---|3| C
    B ---|2| D((라))
    C -.-|5| D
    C ---|6| E((마))
    D -.-|7| E

트리가 다동에서 세 갈래로 뻗습니다. 이 절차에 붙은 이름이 크루스칼 알고리즘입니다.

두 끝이 같은 조각에 있는지에 빨리 답하려고 서로소 집합이라는 자료구조를 씁니다. 원소가 어느 조각에 속하는지 묻는 일과 두 조각을 하나로 합치는 일을 해 줍니다.

아래는 이 절차를 파이썬으로 옮긴 것입니다. parent 는 노드마다 같은 조각의 노드 하나를 가리킵니다. 처음엔 모든 노드가 자기 자신을 가리킵니다. 혼자인 조각이라는 뜻입니다.

자기 자신을 가리키는 노드가 그 조각의 대표입니다. find 는 가리키는 쪽을 따라 올라가 대표를 찾습니다.

edges = [
    (1, "가", "다"), (4, "가", "나"),
    (3, "나", "다"), (2, "나", "라"),
    (5, "다", "라"), (6, "다", "마"),
    (7, "라", "마"),
]

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

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

    tree = []
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru == rv:
            continue
        parent[ru] = rv
        tree.append((u, v, w))
    return tree

sorted(edges) 가 간선을 가중치 순으로 늘어놓습니다. 두 끝의 대표가 같으면 이미 같은 조각이므로 건너뜁니다. 다르면 한 대표가 다른 대표를 가리키게 해서 두 조각을 합칩니다.

예시 그래프에 돌린 결과는 앞 표와 같습니다.

tree = kruskal("가나다라마", edges)
names = [u + v for u, v, _ in tree]
total = sum(w for *_, w in tree)
names  # ['가다', '나라', '나다', '다마']
total  # 12

가장 싼 간선을 골라도 되는 까닭

매 단계에서 지금 가장 좋아 보이는 것을 고르고 되돌리지 않는 방식을 그리디 알고리즘이라고 합니다. 이런 방식은 대개 최적의 답을 놓칩니다. 최소 신장 트리에서는 놓치지 않습니다. 두 성질이 받쳐 주기 때문입니다.

성질을 보기 전에 답이 몇 개인지부터 짚습니다. 가중치가 모두 다르면 최소 신장 트리는 하나뿐입니다. 같은 가중치가 있으면 합이 같은 최소 신장 트리가 여럿일 수 있습니다. 예시 그래프는 가중치가 모두 달라서 답이 하나입니다.

두 성질 가운데 첫째는 컷으로 말합니다. 컷은 그래프의 노드를 두 쪽으로 가르는 것입니다. 예시 그래프에서 마동 하나만 한쪽에 두고 나머지를 다른 쪽에 두면 컷 하나가 됩니다. 이 컷의 두 쪽을 가로지르는 간선은 다–마(6) 과 라–마(7) 둘입니다.

첫째 성질이 컷 성질입니다. 어떻게 가르든, 두 쪽을 가로지르는 간선 가운데 가장 싼 것은 최소 신장 트리 가운데 적어도 하나에 들어 있습니다. 앞의 컷에서는 더 싼 다–마 가 답에 들어 있습니다.

컷 성질이 맞는 까닭은 바꿔치기로 보입니다. 가로지르는 가장 싼 간선 e 가 빠진 최소 신장 트리 T 가 있다고 해 봅니다. T 에 e 를 더하면 사이클이 생깁니다. 이 사이클은 두 쪽을 오가므로 e 말고도 가로지르는 간선 f 를 하나 더 지납니다.

이제 f 를 빼면 다시 신장 트리가 됩니다. e 는 f 보다 비싸지 않으므로 합은 늘지 않습니다. T 가 이미 최소였으니 바꾼 트리도 최소 신장 트리입니다. 그 트리 안에 e 가 들어 있습니다.

둘째는 사이클 성질입니다. 어느 사이클에서 가중치가 혼자 가장 큰 간선은 어느 최소 신장 트리에도 들어가지 않습니다. 그 간선을 빼도 사이클의 나머지 간선으로 두 끝이 이어지기 때문입니다.

예시에서 가–다–나 사이클의 간선은 1 · 3 · 4 입니다. 가장 비싼 가–나(4) 는 앞 표에서 버려졌습니다.

앞의 절차는 두 성질을 옮긴 것입니다. 간선을 넣는 순간, 그 간선의 한쪽 끝이 든 조각과 나머지를 두 쪽으로 가르는 컷을 봅니다. 싼 것부터 봤으니 이 간선이 그 컷을 가로지르는 가장 싼 간선입니다. 그래서 컷 성질에 따라 이 간선은 답에 듭니다.

버린 간선은 그 순간 생기는 사이클에서 가장 비싼 간선입니다. 그래서 사이클 성질이 답에서 뺍니다.

두 성질은 가중치끼리 크기를 비교하기만 합니다. 가중치가 음수가 아니라는 조건을 어디에도 안 씁니다. 그래서 음수 가중치가 섞여도 같은 절차로 답을 구합니다.

답을 구하는 세 알고리즘

최소 신장 트리를 구하는 대표 알고리즘은 셋입니다. 셋 다 컷 성질로 간선을 하나씩 확정합니다. 갈리는 것은 어떤 컷을 보느냐입니다.

크루스칼 알고리즘은 앞에서 본 절차입니다. 간선 전체를 가중치 순으로 정렬해 싼 것부터 봅니다. 보는 컷은 넣는 간선의 한쪽 끝이 든 조각과 나머지 사이입니다. 흩어진 조각들이 조금씩 합쳐져 답이 됩니다.

프림 알고리즘은 노드 하나에서 출발해 트리 하나를 키웁니다. 보는 컷은 지금 트리와 나머지 노드 사이입니다. 그 컷을 가로지르는 간선 가운데 가장 싼 것을 하나씩 붙입니다.

다음 간선을 빨리 고르려고 프림은 우선순위 큐를 씁니다. 우선순위 큐는 넣어 둔 값 가운데 가장 작은 것을 먼저 꺼내 주는 자료구조입니다. 프림은 트리에 붙일 후보 간선을 가중치를 값으로 삼아 넣어 둡니다.

우선순위 큐는 흔히 이진 힙으로 만듭니다. 가장 작은 값이 늘 맨 위에 오도록 값을 나무 모양으로 매달아 두는 구조입니다.

예시 그래프에서 가동부터 프림 알고리즘을 돌리면 다, 나, 라, 마 순서로 붙습니다. 붙는 순서는 크루스칼과 달라도 나오는 트리는 같습니다.

보루프카 알고리즘은 모든 조각이 한꺼번에 움직입니다. 처음엔 노드 하나하나가 따로 조각입니다. 한 바퀴마다 조각마다 바깥으로 나가는 가장 싼 간선을 하나씩 고릅니다. 고른 간선은 모두 넣습니다. 그러면 조각 수가 한 바퀴에 적어도 절반으로 줍니다.

예시 그래프라면 첫 바퀴에 가–다 · 나–라 · 다–마 가 들어가 조각이 {가, 다, 마} 와 {나, 라} 둘로 줍니다. 둘째 바퀴에 나–다 가 들어가 끝납니다.

걸리는 시간

그래프가 커질 때 걸리는 시간이 어떻게 늘어나는지를 노드 수 V 와 간선 수 E 로 따집니다. 이런 늘어남은 빅오 표기법으로 적습니다. 빅오 표기법은 입력이 커질 때 비용이 어떤 모양으로 따라 커지는지를 적는 약속입니다.

프림 알고리즘은 다음 간선을 고르는 방법이 둘입니다. 하나는 이진 힙으로 만든 우선순위 큐를 쓰는 방법입니다. 다른 하나는 노드마다 트리에 붙는 가장 싼 비용을 표에 적어 두고 매번 처음부터 훑는 방법입니다. 아래 표에 두 방법을 따로 적었습니다.

아래 표의 log V 는 V 를 1 이 될 때까지 반으로 나눈 횟수입니다. 노드가 백만 개여도 스무 번 남짓입니다.

크루스칼의 O(E log E) 와 O(E log V) 는 빅오로는 같습니다. 간선 수는 노드 수의 제곱을 넘지 않습니다. 그래서 log E 는 2 log V 를 넘지 않습니다. 빅오 표기법은 이런 상수 배를 뗍니다.

프림의 두 줄은 그래프의 모양에 따라 갈립니다. 간선이 노드 수의 제곱에 가까울 만큼 빽빽하면 E log V 가 V² 보다 커지므로 표를 훑는 쪽이 덜 걸립니다. 도로망처럼 노드마다 이웃이 몇 개뿐이면 힙 쪽이 덜 걸립니다.

쓰는 메모리는 셋 다 노드 수와 간선 수를 더한 만큼에 비례합니다. 크루스칼은 정렬한 간선 목록을, 프림은 우선순위 큐를 들고 있습니다.

최단 경로와 다른 점

최소 신장 트리는 최단 경로 문제와 자주 헷갈립니다. 최단 경로 문제는 두 노드 사이에서 가중치 합이 가장 작은 길을 찾습니다. 최소 신장 트리가 줄이는 것은 트리 전체의 합이지 두 노드 사이의 길이 아닙니다.

예시에서 라동과 마동을 보면 둘이 갈립니다. 최소 신장 트리 위에서 라동에서 마동으로 가려면 라–나–다–마 를 지나 2 + 3 + 6 으로 11 이 듭니다. 원래 그래프에서는 라–마 간선 하나로 7 이면 갑니다.

한 출발점에서 모든 노드까지 가는 가장 짧은 길만 모아도 트리가 됩니다. 이 트리를 최단 경로 트리라고 따로 부릅니다. 모든 노드를 덮으니 이것도 신장 트리입니다. 줄이는 것은 출발점에서 각 노드까지의 거리입니다.

다익스트라 알고리즘이 최단 경로 트리를 만듭니다. 다익스트라는 프림과 뼈대가 같습니다. 우선순위 큐에 넣는 값만 다릅니다. 프림은 간선 하나의 가중치를, 다익스트라는 출발점부터 더한 거리를 넣습니다.

네트워크 장비의 STP(Spanning Tree Protocol, 스패닝 트리 프로토콜)도 이름 때문에 헷갈립니다. 스위치끼리 고리 모양으로 이어져 있으면 같은 데이터가 망을 끝없이 돕니다. STP 는 이 고리를 끊으려고 신장 트리를 만듭니다.

STP 가 만드는 트리는 기준으로 정한 스위치 하나까지 가는 비용이 가장 작은 길을 모은 것입니다. 그래서 최소 신장 트리보다 최단 경로 트리에 가깝습니다.

조건이 바뀐 변형

입력 그래프가 조금 다르면 문제도 조금 바뀝니다. 흔히 만나는 변형 셋을 봅니다.

그래프가 몇 조각으로 끊겨 있으면 신장 트리가 없습니다. 이때는 조각마다 최소 신장 트리를 구해 모은 최소 신장 숲을 답으로 삼습니다. 크루스칼과 보루프카는 손대지 않아도 숲을 냅니다. 프림은 출발점이 든 조각만 덮고 멈추므로 남은 조각마다 다시 돌립니다.

가중치 합이 가장 큰 신장 트리를 최대 신장 트리라고 합니다. 가중치의 부호를 모두 뒤집고 최소 신장 트리를 구하면 됩니다. 크루스칼이라면 비싼 간선부터 보면 됩니다.

간선에 방향이 있으면 앞의 세 알고리즘은 맞는 답을 보장하지 못합니다. 이때는 노드 하나를 뿌리로 정합니다. 뿌리는 모든 길이 시작하는 노드입니다.

뿌리에서 모든 노드로 내려가는 가장 싼 트리를 찾는 문제가 따로 있습니다. 에드먼즈 알고리즘이 이 문제를 풉니다.

최소 신장 트리가 쓰이는 곳

모든 지점을 가장 싸게 잇는 설계에 바로 쓰입니다. 통신망 케이블, 전력선, 수도관처럼 여러 지점을 한 망으로 묶는 배선이 그렇습니다. 지점이 노드, 놓을 수 있는 구간이 간선, 공사비가 가중치가 됩니다.

비슷한 것끼리 묶는 군집 분석에도 쓰입니다. 데이터 하나하나를 노드로, 두 데이터가 서로 다른 정도를 가중치로 둡니다. 묶고 싶은 무리 수를 k 라 합니다. 최소 신장 트리에서 가장 비싼 간선을 k − 1 개 끊으면 k 개의 조각이 남습니다. 이렇게 묶는 방식을 단일 연결 군집이라고 합니다.

외판원 순회는 모든 도시를 한 번씩 들르고 출발점으로 돌아오는 가장 짧은 길을 찾는 문제입니다. 도시가 늘면 정확한 답을 빨리 구하는 방법이 알려져 있지 않습니다. 최소 신장 트리는 이 답을 어림하는 데 쓰입니다.

어림에는 조건이 하나 붙습니다. 두 도시 사이를 곧장 가는 길이 다른 도시를 거쳐 가는 길보다 길지 않아야 합니다. 이 조건을 삼각 부등식이라고 합니다.

어림이 맞는 까닭은 세 단계로 봅니다. 먼저 최소 신장 트리의 합은 가장 짧은 순회보다 크지 않습니다. 가장 짧은 순회에서 간선 하나를 빼면 신장 트리가 되기 때문입니다.

다음으로 최소 신장 트리로 순회를 만듭니다. 한 도시에서 출발해 간선마다 갔다가 되돌아오며 트리를 한 바퀴 훑습니다. 간선마다 두 번 지나므로 이 길의 길이는 트리 합의 두 배입니다.

이 길은 같은 도시를 여러 번 들릅니다. 이미 들른 도시는 건너뛰고 다음 도시로 곧장 갑니다. 삼각 부등식 덕에 곧장 가도 길이 늘지 않습니다. 그래서 이렇게 만든 순회는 가장 짧은 순회의 두 배를 넘지 않습니다.

관련 항목

최소 신장 트리가 속하는 상위 분류

알고리즘 · 그래프 알고리즘 · 조합 최적화 · 그리디 알고리즘 · 그래프

최소 신장 트리를 이루는 그래프의 구성 요소

노드 · 간선 · 가중치 · 가중 그래프 · 무방향 그래프 · 연결 그래프 · 사이클 · 트리 · 신장 트리

최소 신장 트리를 구하는 알고리즘

프림 알고리즘 · 크루스칼 알고리즘 · 보루프카 알고리즘 · 역삭제 알고리즘

최소 신장 트리 알고리즘이 쓰는 자료구조

우선순위 큐 · 힙 · 이진 힙 · 피보나치 힙 · 서로소 집합 · 유니온 파인드 · 인접 리스트 · 인접 행렬 · 간선 리스트

최소 신장 트리의 답을 보장하는 성질

컷 성질 · 사이클 성질 · 탐욕 선택 속성 · 최적 부분 구조

최소 신장 트리와 헷갈리는 이웃

최단 경로 · 최단 경로 트리 · 다익스트라 알고리즘 · 스패닝 트리 프로토콜 · 스타이너 트리

최소 신장 트리를 바꿔 푸는 변형 문제

최소 신장 숲 · 최대 신장 트리 · 병목 신장 트리 · 에드먼즈 알고리즘

최소 신장 트리로 푸는 문제

네트워크 설계 · 군집 분석 · 단일 연결 군집 · 외판원 순회 · 근사 알고리즘 · 삼각 부등식

걸리는 시간을 적는 표기

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 로그 함수