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

크루스칼 알고리즘은 최소 비용 신장 트리(MST, Minimum Spanning Tree)를 찾는 알고리즘으로, 그리디(탐욕법, Greedy) 알고리즘을 기반으로 동작합니다. 그래프의 모든 정점을 최소 비용으로 연결하는 간선을 선택하는 방식입니다.

Table of Contents

Toggle

1. 알고리즘 동작 과정

간선 리스트 정렬
- 모든 간선을 가중치 기준으로 오름차순 정렬합니다.
사이클을 방지하며 MST 구성
- 간선을 하나씩 선택하며 두 정점이 같은 집합에 속하지 않으면(사이클이 발생하지 않으면) 트리에 추가합니다.
- 유니온 파인드(Union-Find) 자료구조를 사용하여 두 정점이 같은 집합에 속하는지 확인합니다.
정점 개수 – 1개의 간선이 선택되면 종료
- 신장 트리는 정점이 VVV개라면, 반드시 V−1V-1V−1개의 간선만 포함해야 합니다.

2. 크루스칼 알고리즘 코드 구현 (Python)

# 크루스칼 알고리즘 (Kruskal's Algorithm)
class DisjointSet:
    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):
        rootX = self.find(x)
        rootY = self.find(y)

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

def kruskal(graph, V):
    mst = []  # 최소 신장 트리에 포함될 간선 리스트
    edges = sorted(graph, key=lambda x: x[2])  # 간선을 가중치 기준으로 정렬
    ds = DisjointSet(V)

    for u, v, weight in edges:
        if ds.find(u) != ds.find(v):  # 사이클이 발생하지 않으면 추가
            ds.union(u, v)
            mst.append((u, v, weight))

    return mst

# 예제 그래프 (정점 개수: 4)
edges = [
    (0, 1, 1),
    (1, 2, 2),
    (0, 2, 4),
    (2, 3, 3),
    (1, 3, 5)
]

mst = kruskal(edges, 4)
print("최소 신장 트리:", mst)

3. 크루스칼 알고리즘 복잡도

4. 크루스칼 알고리즘 vs 프림 알고리즘

	크루스칼 알고리즘	프림 알고리즘
기본 개념	간선을 가중치 기준으로 선택	하나의 정점에서 시작
구현 방식	간선을 정렬 후 선택	우선순위 큐(힙)를 사용하여 정점 중심 선택
시간 복잡도	O(Elog⁡E)O(E \log E)O(ElogE)	O(Elog⁡V)O(E \log V)O(ElogV) (힙 사용 시)
적합한 그래프	희소 그래프 (Sparse)	밀집 그래프 (Dense)