크루스칼 알고리즘(Kruskal's Algorithm) - Minimum Spanning Tree (MST)

1. 개요

Kruskal's Algorithm은 최소 스패닝 트리(Minimum Spanning Tree, MST) 를 찾는 대표적인 알고리즘 중 하나다.
그래프의 모든 정점을 연결하면서 간선 비용(가중치) 의 합이 최소가 되도록 스패닝 트리를 구성한다.
에지 리스트(Edge List)를 가중치 오름차순으로 정렬한 뒤, 사이클(Cycle)이 생기지 않도록 Union-Find(Disjoint Set) 자료구조를 활용하여 순차적으로 간선을 선택한다.

---

2. 기본 아이디어

1. 모든 간선을 가중치 오름차순으로 정렬
2. 가장 낮은 가중치 간선부터 차례대로 확인
3. 사이클이 발생하지 않으면(Union-Find로 검사) 스패닝 트리에 포함
4. 모든 정점을 연결할 때까지(또는 간선을 V - 1개 선택 시) 반복

---

3. 시간 복잡도

• 일반적으로 간선을 정렬하는 데 O(E log E)
• Union-Find 연산(Union, Find)은 거의 상수 시간(경로 압축, 랭크 사용 시)
• 전체적으로 O(E log E) 가 대표적인 복잡도

---

4. Kruskal's Algorithm 코드 예제 (Java)

아래 예시는 간선 리스트와 Union-Find를 사용해 Kruskal 알고리즘으로 MST를 구하는 예시다.

4.1 소스 코드

import java.util.*;

class Edge implements Comparable<Edge> {
    int u;
    int v;
    int weight;

    public Edge(int u, int v, int weight) {
        this.u = u;
        this.v = v;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

public class KruskalExample {
    private int[] parent; // Union-Find용 부모 배열
    private int[] rank;   // Union-Find용 랭크

    public KruskalExample(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    // Find 연산: 루트 노드 찾기 (경로 압축)
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // Union 연산: 두 집합을 합침
    public boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA == rootB) {
            // 이미 같은 집합 => 사이클 발생
            return false;
        }

        // 랭크를 기준으로 합침
        if (rank[rootA] < rank[rootB]) {
            parent[rootA] = rootB;
        } else if (rank[rootA] > rank[rootB]) {
            parent[rootB] = rootA;
        } else {
            parent[rootB] = rootA;
            rank[rootA]++;
        }
        return true;
    }

    public int kruskalMST(List<Edge> edges, int vertexCount) {
        // 간선 가중치 기준으로 정렬
        Collections.sort(edges);

        int mstCost = 0;
        int edgeCount = 0;

        // 가중치 오름차순으로 간선을 확인
        for (Edge e : edges) {
            // 두 정점이 다른 집합에 속한다면(사이클 X)
            if (union(e.u, e.v)) {
                // MST에 포함
                mstCost += e.weight;
                edgeCount++;
                // 모든 정점을 연결하면 종료 (MST는 V-1개 간선으로 구성)
                if (edgeCount == vertexCount - 1) {
                    break;
                }
            }
        }
        return mstCost;
    }
}

4.2 테스트 코드

import java.util.*;

public class KruskalTest {
    public static void main(String[] args) {
        // 정점 개수(예: 6)
        int n = 6;
        // KruskalExample 객체 생성
        KruskalExample kruskal = new KruskalExample(n);

        // 간선 리스트 초기화
        List<Edge> edges = new ArrayList<>();
        // (u, v, weight)
        edges.add(new Edge(0, 1, 4));
        edges.add(new Edge(0, 2, 2));
        edges.add(new Edge(1, 2, 5));
        edges.add(new Edge(1, 3, 10));
        edges.add(new Edge(2, 4, 3));
        edges.add(new Edge(2, 5, 7));
        edges.add(new Edge(3, 4, 6));
        edges.add(new Edge(4, 5, 1));

        int result = kruskal.kruskalMST(edges, n);
        System.out.println("MST 비용(가중치 합): " + result);
        // 예시 결과: MST 비용(가중치 합)은 1 + 2 + 3 + 4 + 6 = 16 (혹은 구조 따라 달라질 수 있음)
    }
}

---

5. Kruskal's Algorithm 코드 예제 (Python)

아래 예시는 Python에서 간선 리스트와 Union-Find를 이용한 Kruskal 예시다.

5.1 소스 코드

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in 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, a, b):
        rootA = self.find(a)
        rootB = self.find(b)

        if rootA == rootB:
            return False  # cycle 발생

        if self.rank[rootA] < self.rank[rootB]:
            self.parent[rootA] = rootB
        elif self.rank[rootA] > self.rank[rootB]:
            self.parent[rootB] = rootA
        else:
            self.parent[rootB] = rootA
            self.rank[rootA] += 1
        return True

def kruskal_mst(edges, vertex_count):
    # edges: [(weight, u, v), ...] 형태 권장
    # 가중치 기준으로 정렬
    edges.sort(key=lambda x: x[0])

    uf = UnionFind(vertex_count)
    mst_cost = 0
    edge_count = 0

    for weight, u, v in edges:
        if uf.union(u, v):
            mst_cost += weight
            edge_count += 1
            if edge_count == vertex_count - 1:
                break

    return mst_cost

5.2 테스트 코드

def test_kruskal():
    n = 6  # 정점 개수
    # (weight, u, v) 순으로 구성
    edges = [
        (4, 0, 1),
        (2, 0, 2),
        (5, 1, 2),
        (10, 1, 3),
        (3, 2, 4),
        (7, 2, 5),
        (6, 3, 4),
        (1, 4, 5),
    ]

    result = kruskal_mst(edges, n)
    print("MST 비용(가중치 합):", result)
    # 예시 결과 예: 16

if __name__ == "__main__":
    test_kruskal()

---

6. 활용 예시

1. 최소 스패닝 트리(MST)
   • 네트워크(통신, 전력 등)의 연결 비용 최소화.
   • Prim, Kruskal, Borůvka 등이 대표적인 MST 알고리즘.
2. 최소 비용 인프라 건설
   • 도시 간 도로, 파이프라인 등 인프라 구축 시, 비용을 최소화하며 모든 도시를 연결.
3. 청소 로봇, 전선 설치 등
   • 그래프 기반의 연결 비용이 중요한 문제에 적용 가능.

---

7. Prim 알고리즘과의 비교

항목 Kruskal’s Algorithm Prim’s Algorithm

자료 구조	간선 리스트를 정렬 후 Union-Find 사용	우선순위 큐(Heap) + 인접 리스트/행렬로 구현 가능
구현 난이도	Union-Find를 이용한 간단 구현 (에지 정렬 필수)	그래프 구조(인접 리스트/행렬)에 따라 구현 방식 상이
권장 상황	간선이 적은 희소 그래프에 유리	정점이 적거나, 혹은 모든 정점이 고르게 연결된 밀집 그래프일 때 유리

---

8. 결론

• Kruskal's Algorithm은 간선을 가중치 오름차순으로 정렬하고, 사이클을 피하기 위해 Union-Find를 사용하는 방식의 MST 알고리즘이다.
• 시간 복잡도는 간선 정렬에 의해 O(E log E)가 일반적이며, 최대 V - 1개 간선만 선택하면 MST가 완성된다.
• Prim 알고리즘과 더불어 MST 문제에서 대표적으로 쓰이며, 에지 중심적 접근이 필요한 상황(간선이 희소한 그래프 등)에서 효과적이다.