크루스칼 알고리즘 (Kruskal Algorithm)

최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 대표적인 알고리즘 중 하나인 크루스칼 알고리즘은 그리디 알고리즘(Greedy Algorithm)을 기반으로 설계되었습니다. 이 알고리즘은 간선(Edge)을 하나씩 추가하면서 MST를 구성합니다.

---

크루스칼 알고리즘의 주요 특징

1. 간선 중심 접근 방식
   • 그래프의 모든 간선을 가중치 순으로 정렬한 뒤, 작은 가중치부터 간선을 하나씩 선택합니다.
2. 사이클 방지
   • Union-Find(Disjoint Set) 자료구조를 사용하여 간선을 추가할 때 사이클이 생기는지 확인합니다.
3. 시간 복잡도
   • 간선 정렬: $( O(E log E) )$
   • Union-Find 연산: $( O(E cdot alpha(V)) )$, 여기서 $( alpha(V) )$는 역아커만 함수로 매우 작습니다.
   • 따라서 전체 시간 복잡도는 $( O(E log E) )$입니다.

---

크루스칼 알고리즘의 동작 과정

1. 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬합니다.
2. Union-Find 자료구조를 초기화합니다.
3. 가중치가 가장 낮은 간선부터 하나씩 선택하며, 다음 조건에 따라 처리합니다:
   • 간선을 추가했을 때 사이클이 발생하지 않으면 간선을 MST에 추가합니다.
   • 사이클이 발생하면 해당 간선을 제외합니다.
4. 모든 정점이 연결될 때까지(즉, MST의 간선 개수가 $( V-1 )$개가 될 때까지) 위 과정을 반복합니다.

---

파이썬 코드 예제

# Union-Find 구현
class UnionFind:
    def __init__(self, n):
        self.parent = list(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:
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1

def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])  # 간선을 가중치 기준으로 정렬
    uf = UnionFind(n)
    mst = []
    total_weight = 0

    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))
            total_weight += weight

    return mst, total_weight

# 그래프 정의 (정점 수, 간선 리스트)
n = 4
edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]

mst, total_weight = kruskal(n, edges)
print("MST:", mst)
print("Total Weight:", total_weight)

---

결과

위 코드에서 그래프는 다음과 같이 표현됩니다:

• 정점: 4개 (0, 1, 2, 3)
• 간선: 5개 (가중치 포함)

출력 예시는 다음과 같습니다:

MST: [(2, 3, 4), (0, 3, 5), (0, 1, 10)]
Total Weight: 19