Union-Find & 크루스칼

Union-Find와 크루스칼 알고리즘 정리

최소 신장 트리(Minimum Spanning Tree, MST)를 구할 때 가장 대표적으로 쓰이는 알고리즘 중 하나가 크루스칼 알고리즘(Kruskal’s Algorithm)이다.
그리고 이 알고리즘의 핵심 자료구조가 바로 Union-Find(또는 Disjoint Set Union, DSU) 이다.

이번 글에서는 Union-Find 원리부터 크루스칼 알고리즘 적용까지 정리해본다.

---

1. Union-Find (Disjoint Set Union, DSU)

Union-Find는 여러 원소가 있을 때, 서로 같은 그룹에 속해 있는지(Find), 두 그룹을 합치는 연산(Union)을 효율적으로 수행할 수 있는 자료구조다.

(1) 기본 아이디어

• 모든 원소는 처음에 자기 자신만을 대표하는 집합을 가진다.

• Find(x): 원소 x가 속한 집합의 대표(root)를 찾는다.

• Union(x, y): 원소 x와 y가 속한 집합을 합친다.

• 대표적인 응용: 네트워크 연결 여부, 그래프의 사이클 판별, MST 구하기 등.

(2) 구현 방법

단순 구현

# 초기화
parent = [i for i in range(n)]  # 처음에는 자기 자신이 부모

def find(x):
    if parent[x] == x:
        return x
    return find(parent[x])

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        parent[root_y] = root_x

최적화 기법

1. 경로 압축

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축
    return parent[x]

2. Union by Rank

rank = [0] * n

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x == root_y:
        return
    if rank[root_x] < rank[root_y]:
        parent[root_x] = root_y
    elif rank[root_x] > rank[root_y]:
        parent[root_y] = root_x
    else:
        parent[root_y] = root_x
        rank[root_x] += 1

(3) 시간 복잡도

• 최적화 전: Find와 Union은 O(n)

• 경로 압축 + Union by Rank 적용 시: 거의 O(1)에 가까운 성능
  → 정확히는 α(n) (아커만 함수의 역함수), 사실상 상수 시간으로 간주

2. 크루스칼 알고리즘 (Kruskal's Algorithm)

최소 신장 트리(MST) 문제를 해결하는 대표적인 알고리즘.
MST란, 모든 정점을 연결하면서 간선의 가중치 합이 최소가 되는 트리를 의미한다.

(1) 알고리즘 절차

Step 1: 가중치가 가장 작은 간선 (2-3, 4) 선택

Step 2: 다음 간선 (0-3, 5) 선택

Step 3: (0-1, 10) 선택 → MST 완성

1. 모든 간선을 가중치 기준으로 오름차순 정렬한다.
2. 작은 간선부터 선택하면서, 사이클이 생기지 않는다면 MST에 포함시킨다.
3. 사이클 판별은 Union-Find로 수행한다.
4. n-1개의 간선이 선택되면 종료한다.

(2) 의사코드

Kruskal(G):
    MST = {}
    모든 간선을 가중치 기준으로 오름차순 정렬
    for 간선 (u, v, w):
        if Find(u) != Find(v):
            Union(u, v)
            MST에 (u, v, w) 추가
    return MST

(3) Python Code

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        return True

def kruskal(n, edges):
    uf = UnionFind(n)
    mst = []
    edges.sort(key=lambda x: x[2])  # 가중치 기준 정렬
    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
    return mst

# 예시: 정점 4개, 간선 5개
edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]
print(kruskal(4, edges))  
# 출력 예시: [(2, 3, 4), (0, 3, 5), (0, 1, 10)]

(4) 시간 복잡도

• 간선 정렬: O(E log E)

• Union-Find 연산: 각 간선마다 O(α(V)) ≈ O(1)

• 최종 시간 복잡도: O(E log E)
  (간선 수 E가 정점 수 V^2에 비해 많을 수 있으므로 정렬이 지배적)

3. 정리

• Union-Find: 집합을 효율적으로 합치고 찾는 자료구조

• 크루스칼 알고리즘: 간선 정렬 + Union-Find 조합으로 MST를 구한다

• 시간 복잡도: O(E log E)

• 응용: 네트워크 최소 비용, 도로 연결, 전력망 설계 등 다양한 최적화 문제