처음에는 크루스칼 알고리즘과 유니온 파인드가 그냥 세트처럼 보일 수 있습니다. 하지만 둘은 억지로 묶인 조합이 아닙니다. 크루스칼이 매 간선마다 던지는 질문을 유니온 파인드가 빠르게 처리해 주기 때문에 자연스럽게 함께 나옵니다.
이 글에서는 최소 신장 트리부터 짚고, 왜 간선을 정렬하는지, 왜 사이클 판별이 핵심인지, 그리고 왜 그 자리에 유니온 파인드가 들어오는지 차근차근 정리하겠습니다.
먼저 MST부터 보자
최소 신장 트리는 가중치가 있는 연결 그래프에서 모든 정점을 연결하되, 사이클 없이, 전체 간선 가중치 합이 가장 작은 트리입니다.
- 모든 정점을 연결해야 합니다.
- 사이클이 있으면 안 됩니다.
- 전체 비용 합이 가장 작아야 합니다.
최소 신장 트리 문제는 결국 싸게 연결하되, 같은 곳을 빙빙 도는 간선은 넣지 말자로 요약할 수 있습니다.
그래프가 연결되어 있지 않다면 하나의 트리를 만들 수 없으므로, 이때는 연결 성분마다 하나씩 만들어지는 최소 신장 포리스트로 이해하면 안전합니다.
크루스칼은 어떻게 움직일까
- 모든 간선을 가중치 오름차순으로 정렬합니다.
- 가장 싼 간선부터 하나씩 봅니다.
- 지금 간선을 넣어도 사이클이 생기지 않으면 채택합니다.
- 사이클이 생기면 버립니다.
- 간선을 정점 수보다 하나 적은 개수만큼 채우면 끝냅니다.
핵심은 가장 싼 간선을 무조건 넣는 것이 아니라, 가장 싼 간선부터 보되 현재 구조를 망치지 않는 간선만 넣는다는 점입니다.
그래서 크루스칼의 질문은 매번 하나입니다. 이 간선을 넣으면 사이클이 생길까.
왜 간선을 먼저 정렬할까
크루스칼은 정점 중심이 아니라 간선 중심으로 움직입니다. 그래서 먼저 해야 할 일은 어떤 간선을 먼저 볼 것인가를 정하는 것입니다.
가중치가 작은 간선부터 보는 이유는 전체 비용을 줄이려는 탐욕적 선택 때문입니다. 비싼 간선을 먼저 보면, 나중에 더 싼 간선을 넣고 싶어도 이미 연결 구조가 굳어서 기회를 놓칠 수 있습니다.
- 제일 싼 간선 먼저
- 그다음으로 싼 간선
- 같은 가중치가 있으면 그 안에서 순서는 달라도 됨
같은 가중치가 있다고 해서 알고리즘이 틀리는 것은 아닙니다. 다만 최소 신장 트리가 하나로 유일하지 않을 수는 있습니다.
왜 사이클 판별이 중요할까
트리는 사이클이 없어야 합니다. 따라서 어떤 간선을 넣을지 결정할 때 가장 중요한 검사는 이 간선이 이미 연결된 두 점을 다시 잇는가 입니다.
같은 덩어리 안에 있는 두 정점을 다시 잇는다면 연결성은 늘어나지 않는데 비용만 추가되고 사이클까지 생깁니다.
- 양 끝 정점이 이미 같은 덩어리 안에 있으면 버립니다.
- 서로 다른 덩어리에 있으면 두 덩어리를 이어 주므로 후보가 됩니다.
왜 유니온 파인드가 붙을까
유니온 파인드는 원소들이 어떤 그룹에 속해 있는지 관리하는 자료구조입니다. 크루스칼 입장에서는 각 정점이 지금 어느 연결 요소에 속해 있는지만 빠르게 알면 됩니다.
- find(u)와 find(v)가 같으면 이미 같은 그룹입니다.
- 그러면 u-v를 추가하는 순간 사이클이 생깁니다.
- find(u)와 find(v)가 다르면 아직 다른 그룹입니다.
- 그러면 이 간선은 두 그룹을 이어 주므로 채택하고 union(u, v)를 합니다.
정렬은 어떤 간선을 먼저 볼지를 해결하고, 유니온 파인드는 이 간선을 받아도 되는지를 해결합니다.
작은 예시로 보자
- 1-2 비용 1
- 2-3 비용 2
- 1-3 비용 3
- 3-4 비용 4
- 2-4 비용 5
처음에는 모든 정점이 자기 자신만의 그룹입니다. 이제 비용이 낮은 간선부터 보면서 서로 다른 그룹일 때만 채택합니다. 세 번째 간선 1-3은 이미 같은 그룹 안을 다시 잇기 때문에 사이클을 만들고, 그래서 버립니다.
정점이 4개이므로 MST 간선은 3개면 충분합니다. 따라서 1-2, 2-3, 3-4를 채택하면 여기서 끝입니다.
파이썬 구현
class DSU:
def __init__(self, n):
self.parent = list(range(n + 1))
self.rank = [0] * (n + 1)
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
ra = self.find(a)
rb = self.find(b)
if ra == rb:
return False
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return True
def kruskal(n, edges):
edges.sort(key=lambda x: x[2])
dsu = DSU(n)
mst_cost = 0
mst_edges = []
for u, v, w in edges:
if dsu.union(u, v):
mst_cost += w
mst_edges.append((u, v, w))
if len(mst_edges) == n - 1:
break
return mst_cost, mst_edges이 코드에서 볼 부분은 세 가지입니다. 간선 정렬, union의 참거짓으로 사이클을 판정하는 부분, 그리고 MST 간선이 n-1개가 되면 멈추는 부분입니다.
유니온 파인드는 왜 빠를까
- find는 정점이 속한 대표 그룹을 찾습니다.
- union은 두 그룹을 합칩니다.
- path compression은 find를 하면서 부모 경로를 짧게 만듭니다.
- union by rank 또는 size는 트리가 한쪽으로 길게 늘어지는 것을 막습니다.
실전에서는 대체로 정렬 비용이 앞에 있고, DSU는 각 간선에서 필요한 연결성 판정을 빠르게 도와준다고 이해하면 충분합니다.
프림과 차이
- 프림은 현재 만들어진 트리 바깥으로 가장 싸게 뻗는 간선을 고릅니다.
- 크루스칼은 그래프 전체 간선을 싼 순서대로 보면서 숲을 합칩니다.
그래서 크루스칼은 유니온 파인드와 특히 잘 붙고, 프림은 우선순위 큐와 더 강하게 연결됩니다.
헷갈리기 쉬운 점
- 유니온 파인드가 MST를 만드는 것은 아니고, 사이클 판별을 빠르게 돕는 부품입니다.
- 가장 싼 간선이라고 무조건 넣는 것은 아닙니다.
- 연결 그래프가 아니면 하나의 MST 대신 최소 신장 포리스트를 생각해야 합니다.
- 같은 가중치가 있어도 알고리즘은 동작하지만 결과 트리가 여러 개 가능할 수 있습니다.
마무리
- 크루스칼은 간선을 싼 순서대로 봅니다.
- 넣었을 때 사이클이 생기면 버립니다.
- 이 판정을 빠르게 하기 위해 유니온 파인드를 씁니다.
- 정렬은 순서를 정하고, DSU는 채택 가능 여부를 판정합니다.
- 이 흐름이 잡히면 크루스칼 구현이 왜 그런 모양인지 자연스럽게 이해됩니다.
관련해서 유니온 파인드 자체가 왜 빠른지 감각을 먼저 잡고 싶다면 유니온 파인드: 왜 빠를까를 함께 보면 좋습니다. 연결성 자체를 BFS와 DFS 관점에서 먼저 보고 싶다면 BFS와 DFS 차이 글, 가중치가 있는 최단 경로와 MST를 구분하고 싶다면 다익스트라와 BFS 비교 글도 이어서 추천할 만합니다.
개념 기준은 Princeton Algorithms의 Minimum Spanning Trees, cp-algorithms의 Kruskal with DSU, cp-algorithms의 Disjoint Set Union 문서를 참고했습니다.
