[알고리즘] 크루스칼(Kruskal) 알고리즘

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

크루스칼 알고리즘은 그래프 내의 모든 정점을 가장 적은 비용으로 연결하는 최소 신장 트리(Minimun Spanning Tree; MST)를 구하는 대표적인 알고리즘 입니다. 

 

신장 트리(Spanning Tree)
그래프의 모든 정점을 포함하면서, 사이클이 없는 부분 그래프

최소 신장 트리(Minimun Spanning Tree)
간선의 가중치 합이 최소인 신장 트리

---

크루스칼 동작 아이디어

가중치가 낮은 간선부터 순서대로 선택하되, 사이클을 형성하는 간선은 제외한다. 사이클 판별에는 유니온-파인드 알고리즘을 사용한다.

 

1. 모든 간선을 가중치 기준 오름차순으로 정렬
2. 간선들을 순서대로 확인하면서
   1. 해당 간선이 사이클을 형성하지 않으면(두 정점의 루트 노드가 다르면) -> MST에 추가
   2. 사이클을 형성하면 -> 건너뜀
3. MST의 간선 수가 (정점수 -1)개가 되면 종료

---

크루스칼 동작 예시

[ 시작 상태 ]

이러한 그래프가 있다고 하자.

i	A	B	C	D	E
p[i]	A	B	C	D	E

 

 

[ 간선 정렬 하기 ]

v1	v2	w
A	B	1
C	E	2
A	C	3
B	C	3
C	D	4
D	E	5
B	D	6

 

 

[ 간선 선택 : A - B ]

순회하지 않은 간선 중 가중치가 1로 제일 작은 A - B 간선을 선택.

A와 B의 부모 정점이 다르기 때문에 사이클이 생기지 않으므로 MST에 추가 가능

B의 부모 정점을 A로 갱신

i	A	B	C	D	E
p[i]	A	B -> A	C	D	E

 

 

[ 간선 선택 : C - E ]

순회하지 않은 간선 중 가중치가 2로 제일 작은 C - E 간선을 선택

C와 E의 부모 정점이 다르기 때문에 사이클이 발생하지 않으므로 MST에 추가 가능

E의 부모 정점을 C로 갱신

i	A	B	C	D	E
p[i]	A	A	C	D	E -> C

 

[ 간선 선택 : A - C ]

순회하지 않은 간선 중 가중치가 제일 작은 A - C 간선을 선택

A와 C의 부모 정점이 다르기 때문에 사이클이 발생하지 않으므로 MST에 추가 가능

C의 부모 정점을 A로 갱신

i	A	B	C	D	E
p[i]	A	A	C -> A	D	C

 

[ 간선 선택 B - C ]

순회하지 않은 간선 중 가중치가 제일 작은 B - C 간선을 선택

하지만 B와 C의 부모 정점이 A로 같으므로 사이클이 발생함 -> MST에서 제외

i	A	B	C	D	E
p[i]	A	A	A	D	C

 

[ 간선 선택 C - D ]

순회하지 않은 간선 중 가중치가 제일 작은 C - D 간선을 선택
C와 D의 부모 정점이 다르기 때문에 사이클이 발생하지 않으므로 MST에 추가 가능
D의 부모 정점을 C로 갱신

 

[ 종료 ]

위 트리는 그래프 내의 모든 정점을 포함하고 있고, (정점수 - 1)개의 간선이 MST에 포함되어 있으므로

MST를 완성했다고 할 수 있다. 

 

---

크루스칼 - 자바 코드

2026.02.27 - [🤔알고리즘] - [알고리즘] 분리(서로소) 집합 - (Union-Find)

[알고리즘] 분리(서로소) 집합 - (Union-Find)

 

import java.util.*;

class Edge implements Comparable<Edge> {
    int v1, v2, weight;

    public Edge(int v1, int v2, int weight) {
        this.v1 = v1;
        this.v2 = v2;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge o) {
        return Integer.compare(this.weight, o.weight);
    }
}

public class Main {
    static int[] parent;

    // Find 연산
    public static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    // Union 연산
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) parent[b] = a;
    }

    public static void main(String[] args) {
        int V = 7; // 정점 개수
        List<Edge> edges = new ArrayList<>();
        
        // 간선 정보 추가 (v1, v2, weight)
        edges.add(new Edge(1, 2, 29));
        edges.add(new Edge(1, 5, 75));
        // ...

        // 1. 가중치 기준 오름차순 정렬
        Collections.sort(edges);

        // 2. 부모 테이블 초기화
        parent = new int[V + 1];
        for (int i = 1; i <= V; i++) parent[i] = i;

        int totalWeight = 0;
        int edgeCount = 0;

        for (Edge edge : edges) {
            // 3. 사이클이 발생하지 않는 경우에만 집합에 포함
            if (find(edge.v1) != find(edge.v2)) {
                union(edge.v1, edge.v2);
                totalWeight += edge.weight;
                edgeCount++;
                if (edgeCount == V - 1) break; 
            }
        }
        System.out.println("최소 비용: " + totalWeight);
    }
}

---

크루스칼 VS 프림

2026.03.11 - [🤔알고리즘] - [알고리즘] 프림(Prim) 알고리즘

[알고리즘] 프림(Prim) 알고리즘

 

크루스칼 알고리즘과 프림 알고리즘 모두 최소 신장 트리(MST)를 찾기 위해 사용되는 대표적인 알고리즘 입니다. 

두 알고리즘은 목적이 같지만, 접근 방식과 사용하는 자료구조가 다르기 때문에

"그래프의 특성(간선의 개수...)"에 따라 적절히 선택할 필요가 있습니다. 

 

	크루스칼	프림
탐색 기준	간선 중심	정점 중심
동작 방식	가중치가 낮은 간선부터 선택	하나의 정점에서 연결된 정점을 확장
핵심 자료구조	분리 집합(Union - Find)	우선 순위 큐
시간 복잡도	$O(ElogE)$	$O(ElogV)$
유리한 경우	간선이 적은 희소 그래프	간선이 많은 밀집 그래프

 

-> 간선(E)의 개수가 정점에 비해 적은 경우 : 간선 정렬에 시간이 적게 드므로, 크루스칼 알고리즘이 유리합니다. 

-> 간선의 개수가 많은 경우 : 간선 정렬 비용이 커지기 떼문에 정점 위주로 탐색하는 프림이 유리합니다.