크루스칼 알고리즘의 모든 것: 이론부터 구현까지 완벽 해부

크루스칼 알고리즘은 컴퓨터 과학에서 중요한 최소 스패닝 트리(MST)를 찾는 대표적인 알고리즘 중 하나입니다. 이 글에서는 크루스칼 알고리즘의 개념, 동작 원리, 그리고 실제 코드 구현까지 다룹니다. 크루스칼 알고리즘은 간선 기반 알고리즘으로, 주로 많은 그래프 문제를 해결하는 데 사용됩니다.

크루스칼 알고리즘의 개요

크루스칼 알고리즘은 1956년에 최초로 소개되었습니다. 이 알고리즘은 그래프의 모든 간선을 적은 비용 순으로 정렬한 후, 사이클이 형성되지 않도록 하나씩 간선을 추가하여 최소 스패닝 트리를 구성하는 방법입니다.

그래프 이론 배경

• 그래프(Graph): 정점(Vertex)과 간선(Edge)으로 구성된 데이터 구조입니다.
• 스패닝 트리(Spanning Tree): 주어진 그래프의 모든 정점을 포함하는 트리입니다. 즉, 그래프의 부분집합으로 간선은 최소한으로 사용됩니다.
• 최소 스패닝 트리(Minimum Spanning Tree, MST): 모든 정점을 연결하면서 전체 간선 가중치의 합이 최소인 스패닝 트리입니다.

크루스칼 알고리즘의 동작 원리

크루스칼 알고리즘은 다음과 같은 단계로 진행됩니다:

1. 그래프의 모든 간선을 가중치 오름차순으로 정렬합니다.
2. 간선을 하나씩 선택하면서, 현재 간선이 잇는 두 정점이 같은 트리에 속해 있지 않다면, 현재 간선을 최소 스패닝 트리에 추가합니다.
3. 간선을 추가했을 때 사이클이 생기지 않도록 합니다. 이를 위해 Union-Find 자료구조를 사용합니다.
4. 모든 정점이 연결될 때까지 반복합니다.

크루스칼 알고리즘의 구현

이제 Python을 사용하여 크루스칼 알고리즘을 구현하는 방법을 살펴보겠습니다. 일반적으로 Union-Find 자료구조를 사용하여 사이클을 방지합니다.

필요한 함수 정의

1. Union-Find 자료구조

python
class UnionFind:
    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

2. 크루스칼 알고리즘 코어 함수

python
def kruskal(n, edges):
    mst = []
    uf = UnionFind(n)

    edges.sort(key=lambda x: x[2])  # 가중치 기준 오름차순 정렬

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

    return mst

예제 실행

이제 몇 가지 예제를 통해 크루스칼 알고리즘이 어떻게 작동하는지 살펴보겠습니다.

python
# 정점 수와 간선 정보
n = 4
edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]

mst = kruskal(n, edges)
print("Minimum Spanning Tree: ", mst)

위 예제에서는 4개의 정점과 5개의 간선이 주어졌으며, 이 간선들 중에서 최소 가중치를 갖는 스패닝 트리를 찾아 출력을 확인할 수 있습니다.

크루스칼 알고리즘의 시간 복잡도

크루스칼 알고리즘의 시간 복잡도는 O(E log E)입니다. 여기서 E는 그래프의 간선 수를 의미합니다. 이는 간선들을 정렬하는 데 필요한 시간에서 옵니다. 최악의 경우를 고려하더라도 크루스칼 알고리즘은 상당히 효율적이며, Union-Find 자료구조 덕분에 추가적인 최적화도 가능합니다.

결론

크루스칼 알고리즘은 그 단순성에도 불구하고 강력한 성능을 가진 알고리즘입니다. 최소 스패닝 트리를 쉽게 찾을 수 있고, 다양한 그래프 문제에서 활용될 수 있습니다. 이 글에서는 크루스칼 알고리즘의 이론적 배경부터 실제 코드 구현까지 자세히 다뤘으며, 이를 통해 적극적으로 문제를 해결하는 데 도움을 주고자 했습니다.