최소 신장 트리 쉽게 이해하기: 크루스칼 알고리즘과 프림 알고리즘

최소 신장 트리가 해결하는 문제

여러 건물을 케이블로, 여러 마을을 도로로, 여러 서버를 네트워크 링크로 연결해야 하고 가능한 연결마다 비용이 있다고 해 봅시다. 모든 장소가 직간접적으로 연결되면서 총비용이 가장 낮아야 합니다. 고리를 만드는 추가 연결은 필요하지 않으므로 답은 트리, 즉 V개의 노드를 정확히 V − 1개의 간선으로 이은 구조입니다. 이 트리가 최소 신장 트리입니다.

MST는 최단 경로 트리가 아닙니다. 한 시작 노드에서 다른 노드까지의 거리가 아니라 모든 간선의 총 가중치를 최소화합니다.

그리디 선택이 통하는 이유: 컷 속성

노드를 임의의 두 그룹으로 나눕니다. 두 그룹 사이를 가로지르는 간선 중 가장 가벼운 간선은 어떤 최소 신장 트리에 속합니다. 두 알고리즘 모두 이 사실에 기대고 있습니다.

모든 간선 가중치가 다르면 MST는 유일하므로 두 알고리즘이 같은 트리를 반환합니다. 가중치가 같은 간선이 있으면 총합이 같은 MST가 여러 개일 수 있습니다.

단계별 예제

노드 5개와 간선 A–B 4, A–C 3, B–C 1, B–D 2, C–D 4, D–E 2, C–E 5로 이루어진 무방향 그래프입니다.

크루스칼 알고리즘, 가중치순으로 정렬한 간선:

A에서 시작하는 프림 알고리즘: {A}에서 나가는 가장 싼 간선은 A–C (3), {A, C}에서는 C–B (1), {A, B, C}에서는 B–D (2), {A, B, C, D}에서는 D–E (2)입니다. 같은 트리이며 총 가중치는 3 + 1 + 2 + 2 = 8입니다.

파이썬으로 구현한 크루스칼 알고리즘

유니온 파인드는 노드마다 부모 포인터를 유지합니다. find는 노드가 속한 컴포넌트의 대표를 반환하며, 두 노드는 대표가 같을 때, 그리고 그때에만 연결되어 있습니다.

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

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving
            x = parent[x]
        return x

    tree, total = [], 0
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:                          # different components: no cycle
            parent[ru] = rv
            tree.append((u, v, w))
            total += w
    return tree, total

nodes = "ABCDE"
edges = [(4, "A", "B"), (3, "A", "C"), (1, "B", "C"), (2, "B", "D"),
         (4, "C", "D"), (2, "D", "E"), (5, "C", "E")]
print(kruskal(nodes, edges))
# ([('B', 'C', 1), ('B', 'D', 2), ('D', 'E', 2), ('A', 'C', 3)], 8)

완전한 유니온 파인드는 트리를 얕게 유지하는 랭크 또는 크기 기준 합치기도 사용합니다. 경로 반분(path halving)만으로도 실제로는 이미 빠릅니다. 트리에 간선이 V − 1개가 되면 반복을 일찍 멈출 수 있습니다.

파이썬으로 구현한 프림 알고리즘

프림 알고리즘에는 인접 리스트가 필요합니다. 다익스트라 알고리즘처럼 지연 삭제를 사용합니다. 트리에서 나가는 모든 간선을 넣고, 반대편 끝이 이미 트리에 있는 간선은 건너뜁니다.

import heapq
from collections import defaultdict

def prim(edges, start):
    graph = defaultdict(list)
    for w, u, v in edges:
        graph[u].append((w, u, v))
        graph[v].append((w, v, u))
    in_tree = {start}
    heap = list(graph[start])
    heapq.heapify(heap)
    tree, total = [], 0
    while heap:
        w, u, v = heapq.heappop(heap)
        if v in in_tree:
            continue
        in_tree.add(v)
        tree.append((u, v, w))
        total += w
        for edge in graph[v]:
            if edge[2] not in in_tree:
                heapq.heappush(heap, edge)
    return tree, total

print(prim(edges, "A"))
# ([('A', 'C', 3), ('C', 'B', 1), ('B', 'D', 2), ('D', 'E', 2)], 8)

시간 복잡도와 공간 복잡도

E는 많아야 V²이므로 log E는 많아야 2 log V입니다. 따라서 O(E log E)와 O(E log V)는 같은 차수입니다.

변형과 흔한 실수

• 연결되지 않은 그래프: 신장 트리는 존재하지 않습니다. 이때 크루스칼은 최소 신장 포레스트(컴포넌트마다 트리 하나)를 반환하고, 한 시작점에서의 프림은 그 시작점의 컴포넌트만 다룹니다. 트리의 간선이 V − 1개인지 확인하세요.
• 최대 신장 트리: 간선을 내림차순으로 정렬하거나 가중치의 부호를 바꿉니다. 두 알고리즘 모두 음수 가중치도 문제없습니다.
• 방향 그래프에는 다른 알고리즘(최소 유향 신장 트리, Chu-Liu/Edmonds)이 필요하며 크루스칼과 프림은 적용되지 않습니다.
• 클러스터링: 크루스칼을 실행하다가 컴포넌트가 k개 남으면 멈춥니다. 결과는 k개 그룹으로 나눈 단일 연결(single-linkage) 클러스터링입니다.
• 1926년의 보루프카(Borůvka) 알고리즘은 모든 컴포넌트에서 가장 싼 간선을 한꺼번에 추가하며 병렬화에 적합합니다.

언제 쓰는지와 실제 활용

• 네트워크 설계: 어떤 연결 구조든 괜찮을 때 케이블, 배관, 도로로 지점들을 가장 싸게 연결하는 방법.
• 근사 알고리즘: 거리 함수를 만족하는 외판원 문제에서 MST로 최적 길이의 최대 두 배인 순회 경로를 얻을 수 있습니다.
• MST에서 가장 무거운 간선을 잘라 내는 방식의 클러스터링과 이미지 분할.
• 코딩 인터뷰 문제: 모든 점을 연결하는 최소 비용, 최소 비용으로 도시 연결하기, 마을의 급수 시설 최적화.