크루스칼 알고리즘

크루스칼 알고리즘(Kruskal's Algorithm)이란?

크루스칼 알고리즘은 최소 신장 트리(MST, Minimum Spanning Tree)를 찾기 위한 대표적인 그리디 알고리즘(Greedy Algorithm)입니다. 그래프의 모든 정점을 최소 비용으로 연결하는 문제를 해결하는 데 사용되며, 사이클이 없는 트리를 형성하는 것이 핵심입니다.

크루스칼 알고리즘은 가중치가 가장 작은 간선부터 선택하여 트리를 확장해 나가는 방식으로 동작합니다. 알고리즘의 핵심은 간선의 선택 과정에서 사이클이 발생하지 않도록 관리하는 것입니다.

---

1. 최소 신장 트리(MST)란?

신장 트리(Spanning Tree)는 그래프의 모든 정점을 포함하면서, 사이클이 없고 최소한의 간선만으로 연결된 트리를 의미합니다. **최소 신장 트리(MST)**는 여러 신장 트리 중에서도 간선들의 가중치 합이 가장 작은 트리입니다.

• 연결 그래프(Connected Graph): 그래프의 모든 노드가 서로 연결되어 있는 상태.
• 최소 신장 트리: 주어진 그래프에서 모든 노드를 연결하는 트리 중 가중치 합이 최소인 트리.

크루스칼 알고리즘은 이러한 최소 비용의 연결을 구하는 문제에 널리 활용됩니다.

---

2. 크루스칼 알고리즘의 동작 방식

크루스칼 알고리즘은 다음과 같은 절차로 동작합니다:

1. 간선들을 가중치 순으로 정렬합니다.
2. 가장 작은 가중치의 간선부터 선택합니다.
3. 간선이 사이클을 형성하지 않으면 선택한 간선을 신장 트리에 포함시킵니다.
4. 모든 노드를 연결할 때까지 이 과정을 반복합니다.

2.1. 간단한 예시

아래의 그래프에서 크루스칼 알고리즘을 적용해봅시다.

A -- 1 -- B
|        /  |
4       2   3
|   /       |
C -- 5 -- D

1. 모든 간선을 가중치 순으로 정렬: (A-B: 1), (B-C: 2), (B-D: 3), (A-C: 4), (C-D: 5)
2. 가장 작은 간선 (A-B: 1)을 선택하고 트리에 추가.
3. 다음 간선 (B-C: 2)을 선택. 사이클이 생기지 않으므로 추가.
4. (B-D: 3)을 선택하고 트리에 추가.
5. (A-C: 4)는 사이클을 형성하므로 무시.
6. (C-D: 5)는 이미 모든 노드가 연결되었으므로 선택하지 않음.

결과적으로 최소 신장 트리는 A-B-C-D로 구성되고, 가중치의 총합은 6입니다.

---

3. 크루스칼 알고리즘의 구현

크루스칼 알고리즘은 서로소 집합 자료 구조(Union-Find)를 이용하여 구현됩니다.
이 자료 구조를 사용하면 사이클을 효율적으로 관리할 수 있습니다.

# 크루스칼 알고리즘 (Python)

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
            else:
                self.parent[root_u] = root_v
                if self.rank[root_u] == self.rank[root_v]:
                    self.rank[root_v] += 1

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

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

# 예시 그래프 (정점 수, 간선 리스트)
n = 4
edges = [(0, 1, 1), (1, 2, 2), (1, 3, 3), (0, 2, 4), (2, 3, 5)]
mst = kruskal(n, edges)
print("최소 신장 트리:", mst)

3.1. 코드 설명

• DisjointSet: Union-Find 구조를 사용해 사이클을 방지.
• kruskal 함수: 간선을 가중치 순으로 정렬한 후, 사이클이 발생하지 않으면 해당 간선을 선택하여 최소 신장 트리에 포함.

---

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

• 간선 정렬: O(E log E) (E는 간선의 수)
• Union-Find 연산: O(E log V) (V는 정점의 수)

따라서 크루스칼 알고리즘의 전체 시간 복잡도는 O(E log E)입니다.

---

5. 크루스칼 알고리즘의 응용 사례

5.1. 네트워크 설계

크루스칼 알고리즘은 통신 네트워크 구축에서 최소 비용으로 모든 노드를 연결하는 데 유용합니다. 예를 들어, 도시 간의 통신 네트워크를 최적화하는 데 사용할 수 있습니다.

5.2. 전력망 설계

최소 비용으로 여러 지역을 연결하여 전력을 공급하는 전력망 설계에서도 크루스칼 알고리즘이 사용됩니다.

5.3. 도로 건설

도로 네트워크에서 여러 도시를 최소 비용으로 연결하는 최적의 경로를 찾는 데 자주 사용됩니다.

---

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

• 크루스칼 알고리즘은 간선 중심의 알고리즘으로, 간선이 적은 희소 그래프(Sparse Graph)에서 효율적입니다.
• 프림 알고리즘은 노드 중심으로 동작하며, 간선이 많은 밀집 그래프(Dense Graph)에서 더 적합합니다.

두 알고리즘 모두 최소 신장 트리를 찾는 데 효과적이지만, 적용하는 그래프의 특성에 따라 선택이 달라질 수 있습니다.

---

크루스칼 알고리즘은 가중치가 작은 간선부터 선택하여 사이클이 없는 최소 신장 트리를 만드는 효율적인 방법입니다.
그리디 알고리즘의 특성을 잘 활용하여, 다양한 최적화 문제에서 중요한 역할을 합니다.
네트워크 설계, 전력망 최적화, 도로 건설 등 다양한 실제 문제에서 크루스칼 알고리즘의 응용이 가능합니다.