최소 스패닝 트리는 그래프의 모든 정점을 연결하되, 선택한 간선의 비용 합이 최소가 되는 트리입니다. 크루스칼 알고리즘은 이 문제를 간선 중심으로 풉니다.
핵심은 싼 간선부터 고르되, 사이클을 만드는 간선은 버리는 것입니다. 여기서 간선 정렬과 유니온 파인드가 만납니다.
최소 스패닝 트리는 무엇을 최소화할까
정점이 n개라면 스패닝 트리는 모든 정점을 연결하면서 간선이 n-1개인 구조입니다. 여기에 간선 비용 합이 가장 작은 조건이 붙으면 최소 스패닝 트리입니다.
네트워크 연결, 도로 연결, 배선 비용처럼 모두 연결하되 총 비용을 줄이고 싶은 문제에서 떠올릴 수 있습니다.
왜 간선을 정렬할까
그림처럼 크루스칼은 그래프 전체를 한 번에 그리려 하지 않습니다. 정렬된 간선 목록을 앞에서부터 보며, 지금 선택해도 사이클이 생기지 않는 간선만 남깁니다.
크루스칼은 가장 싼 간선부터 봅니다. 싼 간선이 항상 정답이라는 뜻은 아니지만, 사이클을 만들지 않는 한 먼저 선택해도 전체 비용을 줄이는 방향으로 안전합니다.
이 직관은 cut property로 설명할 수 있지만, 처음에는 ‘서로 떨어진 두 덩어리를 가장 싼 간선으로 잇는다’ 정도로 이해해도 충분합니다.
왜 사이클을 막아야 할까
트리는 사이클이 없어야 합니다. 이미 연결된 두 정점을 또 연결하면 새로운 길이 생기는 것이 아니라 빙 도는 길이 하나가 추가됩니다. 이 간선은 모든 정점을 연결하는 데 꼭 필요하지 않습니다.
그래서 크루스칼은 간선을 볼 때마다 두 정점이 이미 같은 컴포넌트에 있는지 확인합니다.
유니온 파인드의 역할
이 표처럼 유니온 파인드는 MST의 비용을 계산하는 도구가 아닙니다. 비용 순서는 정렬이 담당하고, 유니온 파인드는 선택해도 되는 간선인지 빠르게 판정합니다.
유니온 파인드는 정점들이 어떤 연결 그룹에 속하는지 빠르게 관리합니다. find로 대표를 찾고, union으로 두 그룹을 합칩니다.
두 정점의 대표가 같으면 이미 연결된 것이므로 그 간선을 선택하면 사이클이 생깁니다. 대표가 다르면 그 간선을 선택하고 두 그룹을 합칩니다.
Python 구현
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, rank, a, b):
ra, rb = find(parent, a), find(parent, b)
if ra == rb:
return False
if rank[ra] < rank[rb]:
ra, rb = rb, ra
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1
return True
def kruskal(n, edges):
parent = list(range(n))
rank = [0] * n
total = 0
chosen = []
for cost, a, b in sorted(edges):
if union(parent, rank, a, b):
total += cost
chosen.append((a, b, cost))
if len(chosen) == n - 1:
break
return total, chosen이 구현에서 정렬은 선택 후보의 순서를 정하고, union-find는 그 선택이 사이클을 만드는지 검사합니다. 자세한 정당화와 구현 변형은 cp-algorithms의 Kruskal 문서도 참고할 수 있습니다.
Prim과는 무엇이 다를까
Prim은 정점 집합을 키워 가는 느낌이고, Kruskal은 간선을 싼 순서대로 보며 여러 컴포넌트를 합치는 느낌입니다. 문제에서 간선 목록이 주어지고 union-find를 쓰기 쉬우면 Kruskal이 편합니다.
MST를 언제 떠올릴지는 최소 스패닝 트리, 언제 떠올릴까 글과 함께 보면 좋습니다.
정리
최소 스패닝 트리에서 간선 정렬은 싼 후보부터 보기 위한 장치이고, 유니온 파인드는 사이클을 막는 장치입니다. 두 역할을 분리해서 보면 크루스칼 알고리즘이 훨씬 덜 복잡하게 느껴집니다.
