크루스칼 알고리즘

크루스칼 알고리즘(Kruskal's Algorithm)은 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 알고리즘 중 하나로, 그리디 알고리즘(Greedy Algorithm)에 기반하여 동작한다. 그래프의 간선을 가중치가 작은 것부터 정렬한 후, 서로소 집합(Disjoint Set)을 활용하여 최소 비용으로 모든 정점을 연결하는 방법을 찾는다.

1 개요

크루스칼 알고리즘은 간선 중심(edge-based)의 알고리즘으로, 그래프의 모든 간선을 정렬한 후, 사이클을 형성하지 않는 간선을 하나씩 선택하여 최소 신장 트리를 구성한다.

2 동작 과정

• 1. 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다.
• 2. 사이클을 형성하지 않는 간선을 가중치가 작은 것부터 선택한다.
• 3. 서로소 집합(Union-Find)을 사용하여 두 정점이 같은 집합에 속해 있는지 확인한다.
• 4. 같은 집합이 아니라면 해당 간선을 MST에 추가하고, 두 정점을 하나의 집합으로 합친다.
• 5. 모든 정점이 연결될 때까지 위 과정을 반복한다.

3 예제

다음 그래프를 예로 들어 크루스칼 알고리즘의 동작을 살펴보자.

 그래프 (정점: A, B, C, D, E, F, G)
 
 간선 리스트:  
 (A-B, 7), (A-D, 5), (B-C, 8), (B-D, 9), (B-E, 7),  
 (C-E, 5), (D-E, 15), (D-F, 6), (E-F, 8), (E-G, 9), (F-G, 11)

1. 간선을 가중치 기준으로 정렬:
   • (A-D, 5), (C-E, 5), (D-F, 6), (A-B, 7), (B-E, 7),
   • (B-C, 8), (E-F, 8), (B-D, 9), (E-G, 9), (F-G, 11), (D-E, 15)
2. 사이클을 만들지 않으면서 가중치가 작은 간선 선택:
   • 선택된 간선: (A-D), (C-E), (D-F), (A-B), (B-E), (B-C), (E-G)
3. 최소 신장 트리(MST) 결과:
   • (A-D, 5), (C-E, 5), (D-F, 6), (A-B, 7), (B-E, 7), (B-C, 8), (E-G, 9)

4 코드 예제

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)

        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])  # 간선을 가중치 기준으로 정렬
    ds = DisjointSet(n)
    mst = []
    
    for u, v, weight in edges:
        if ds.find(u) != ds.find(v):
            ds.union(u, v)
            mst.append((u, v, weight))

    return mst

# 예제 그래프 (정점 0~6)
edges = [
    (0, 1, 7), (0, 3, 5), (1, 2, 8), (1, 3, 9), (1, 4, 7),
    (2, 4, 5), (3, 4, 15), (3, 5, 6), (4, 5, 8), (4, 6, 9), (5, 6, 11)
]

mst = kruskal(7, edges)
print(mst)

출력 결과 예시:
[(0, 3, 5), (2, 4, 5), (3, 5, 6), (0, 1, 7), (1, 4, 7), (4, 6, 9)]

5 시간 복잡도

크루스칼 알고리즘의 시간 복잡도는 다음과 같다.

• 간선 정렬: O(E log E)
• 서로소 집합 연산(Find, Union): O(α(V)) (거의 상수 시간)
• 최종적으로 O(E log E)로 동작

6 응용

크루스칼 알고리즘은 여러 분야에서 활용된다.

• 네트워크 설계 → 최소 비용으로 네트워크 구축
• 전력망 설계 → 최소 전선 길이로 모든 도시 연결
• 이미지 클러스터링 → 그래프 기반 클러스터링 기법

7 같이 보기

• 최소 신장 트리
• 프림 알고리즘
• 서로소 집합

8 참고 문헌

• Kruskal, Joseph B. "On the shortest spanning subtree of a graph and the traveling salesman problem." Proceedings of the American Mathematical Society, 1956.
• Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.