크루스칼 알고리즘
마지막 업데이트
크루스칼 알고리즘은 최소 신장 트리(MST), 즉 사이클 없이 모든 정점을 연결하는 가장 저렴한 간선 집합을 만듭니다. 모든 간선을 가중치 순으로 정렬한 다음, 아직 연결되지 않은 두 정점을 잇는 한 다음으로 가장 저렴한 간선을 탐욕적으로 추가합니다. 위의 재생 버튼을 눌러 안전하고 저렴한 간선이 하나씩 더해지며 트리가 자라는 모습을 확인하세요.
"이미 연결되어 있는가?" 검사는 union-find(서로소 집합) 자료구조로 수행합니다. 어떤 간선의 두 끝점이 이미 같은 컴포넌트에 있으면 그 간선을 추가할 때 사이클이 생기므로 건너뜁니다. 정렬이 비용을 지배하여 전체적으로 O(E log E)가 됩니다. 크루스칼은 희소 그래프에서 빛을 발합니다.
시간 및 공간 복잡도
| 측정 항목 | 복잡도 | 비고 |
|---|---|---|
| 시간 | O(E log E) | 간선 정렬이 지배적 |
| union-find 연산 | ≈ O(E α(V)) | 경로 압축 시 검사당 거의 상수 시간 |
| 공간 | O(V + E) | 간선 목록 + 서로소 집합 구조 |
| 최적 대상 | 희소 그래프 | 전역 간선 목록에서 동작 |
단계별 과정
| 단계 | 무슨 일이 일어나는가 |
|---|---|
| 1 | 모든 간선을 가중치 오름차순으로 정렬한다. |
| 2 | 각 정점을 자신만의 컴포넌트에 둔다 (union-find). |
| 3 | 다음으로 가장 저렴한 간선을 꺼낸다. |
| 4 | 양 끝점이 서로 다른 컴포넌트에 있으면 트리에 추가하고 둘을 합친다. |
| 5 | 그렇지 않으면 건너뛴다 (사이클이 생긴다). |
| 6 | 트리의 간선이 V − 1개가 되면 멈춘다. |
풀이 예시
정점 A, B, C, D와 간선 A-B(1), B-C(2), A-C(3), C-D(4), B-D(5)를 가진 그래프. 정렬된 간선: A-B(1), B-C(2), A-C(3), C-D(4), B-D(5):
| 간선 (가중치) | 처리 전 컴포넌트 | 동작 |
|---|---|---|
A-B(1) | {A} {B} {C} {D} | 서로 다른 컴포넌트 - MST에 추가하고 {A,B}로 합친다. |
B-C(2) | {A,B} {C} {D} | 서로 다른 컴포넌트 - MST에 추가하고 {A,B,C}로 합친다. |
A-C(3) | {A,B,C} {D} | A와 C는 이미 함께 있음 - 건너뛴다 (사이클이 생긴다). |
C-D(4) | {A,B,C} {D} | 서로 다른 컴포넌트 - MST에 추가하고 {A,B,C,D}로 합친다. |
| 정지 | {A,B,C,D} | 트리에 간선이 V - 1 = 3개. MST = A-B, B-C, C-D, 총 가중치 7. |
크루스칼 알고리즘을 사용해야 할 때
| 이럴 때 사용 | 이럴 때 피하기 |
|---|---|
| 그래프가 희소하다 (정점 대비 간선이 적다). | 그래프가 밀집되어 있다 - 힙을 쓰는 프림이 보통 더 빠르다. |
| 간선이 정렬 가능한 전역 목록으로 이미 주어져 있다. | 간선이 정점마다 훑어야 하는 인접 리스트로만 주어진다. |
| union-find로 뒷받침되는 간단한 구현을 원한다. | 트리가 특정 시작 정점에서부터 자라야 한다. |
| 비연결 그래프의 신장 숲을 만들고 싶다. | 전체 정렬 없이 스트림으로 들어오는 간선을 처리해야 한다. |
Kruskal's Algorithm 코드
Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Kruskal's Algorithm 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.
Python로 구현한 Kruskal's Algorithm 코드
Python
1def find(parent, x):2 while parent[x] != x:3 parent[x] = parent[parent[x]] # path compression4 x = parent[x]5 return x6
7
8def kruskal(vertices, edges):9 # Take the cheapest edge that does not close a cycle10 parent = {v: v for v in vertices}11 mst, total = [], 012 for w, u, v in sorted(edges):13 root_u, root_v = find(parent, u), find(parent, v)14 if root_u != root_v:15 parent[root_u] = root_v16 mst.append((u, v, w))17 total += w18 return mst, total19
20
21vertices = ["A", "B", "C", "D", "E"]22edges = [23 (4, "A", "B"), (1, "A", "C"), (3, "B", "C"), (2, "B", "D"),24 (5, "C", "D"), (6, "C", "E"), (7, "D", "E"),25]26
27mst, total = kruskal(vertices, edges)28for u, v, w in mst:29 print(f"{u} - {v} (weight {w})")30print("Total MST weight:", total)JavaScript로 구현한 Kruskal's Algorithm 코드
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 4], ["A", "C", 2], ["B", "C", 1], ["B", "D", 5],4 ["C", "D", 8], ["C", "E", 10], ["D", "E", 2],5];6
7function kruskal() {8 // Union-find with path compression detects cycles cheaply9 const parent = Object.fromEntries(nodes.map((n) => [n, n]));10 const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));11 const mst = [];12 let total = 0;13 const sorted = [...edges].sort((a, b) => a[2] - b[2]);14 for (const [u, v, w] of sorted) {15 const rootU = find(u);16 const rootV = find(v);17 if (rootU !== rootV) {18 parent[rootU] = rootV;19 mst.push(`${u}-${v} (${w})`);20 total += w;21 }22 }23 return { mst, total };24}25
26const { mst, total } = kruskal();27console.log("MST edges:", mst.join(", "));28console.log("Total weight:", total);Java로 구현한 Kruskal's Algorithm 코드
Java
1import java.util.Arrays;2
3public class Main {4 static int[] parent;5
6 static int find(int x) {7 if (parent[x] != x) parent[x] = find(parent[x]); // path compression8 return parent[x];9 }10
11 static boolean union(int a, int b) {12 int rootA = find(a), rootB = find(b);13 if (rootA == rootB) return false; // would create a cycle14 parent[rootA] = rootB;15 return true;16 }17
18 public static void main(String[] args) {19 int n = 6;20 int[][] edges = {21 {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},22 {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}23 };24 Arrays.sort(edges, (a, b) -> a[2] - b[2]);25 parent = new int[n];26 for (int i = 0; i < n; i++) parent[i] = i;27
28 int total = 0, used = 0;29 for (int[] e : edges) {30 if (union(e[0], e[1])) {31 System.out.println("Take edge " + e[0] + "-" + e[1] + " (weight " + e[2] + ")");32 total += e[2];33 if (++used == n - 1) break;34 }35 }36 System.out.println("MST total weight: " + total);37 }38}C++로 구현한 Kruskal's Algorithm 코드
C++
1#include <algorithm>2#include <iostream>3#include <numeric>4#include <vector>5
6struct Edge {7 int u, v, weight;8};9
10struct DSU {11 std::vector<int> parent;12 explicit DSU(int n) : parent(n) {13 std::iota(parent.begin(), parent.end(), 0);14 }15 int find(int x) {16 if (parent[x] != x) parent[x] = find(parent[x]); // path compression17 return parent[x];18 }19 bool unite(int a, int b) {20 int ra = find(a), rb = find(b);21 if (ra == rb) return false; // would create a cycle22 parent[ra] = rb;23 return true;24 }25};26
27int main() {28 const int n = 5;29 std::vector<Edge> edges = {30 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},31 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},32 };33 // Greedily take the cheapest edge that connects two components34 std::sort(edges.begin(), edges.end(),35 [](const Edge& a, const Edge& b) { return a.weight < b.weight; });36 DSU dsu(n);37 int total = 0;38 std::cout << "MST edges:\n";39 for (const Edge& e : edges) {40 if (dsu.unite(e.u, e.v)) {41 std::cout << " " << e.u << " - " << e.v42 << " (weight " << e.weight << ")\n";43 total += e.weight;44 }45 }46 std::cout << "Total weight: " << total << "\n";47 return 0;48}C로 구현한 Kruskal's Algorithm 코드
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5#define N 56
7typedef struct {8 int u, v, weight;9} Edge;10
11int parent[N];12
13int find(int x) {14 if (parent[x] != x) parent[x] = find(parent[x]); // path compression15 return parent[x];16}17
18bool unite(int a, int b) {19 int ra = find(a), rb = find(b);20 if (ra == rb) return false; // would create a cycle21 parent[ra] = rb;22 return true;23}24
25int cmpEdge(const void* a, const void* b) {26 return ((const Edge*)a)->weight - ((const Edge*)b)->weight;27}28
29int main(void) {30 Edge edges[] = {31 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},32 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},33 };34 int m = sizeof(edges) / sizeof(edges[0]);35 for (int i = 0; i < N; i++) parent[i] = i;36 // Greedily take the cheapest edge that connects two components37 qsort(edges, m, sizeof(Edge), cmpEdge);38 int total = 0;39 printf("MST edges:\n");40 for (int i = 0; i < m; i++) {41 if (unite(edges[i].u, edges[i].v)) {42 printf(" %d - %d (weight %d)\n",43 edges[i].u, edges[i].v, edges[i].weight);44 total += edges[i].weight;45 }46 }47 printf("Total weight: %d\n", total);48 return 0;49}크루스칼 알고리즘 자주 묻는 질문
최소 신장 트리란 무엇인가요?
연결된 가중 그래프의 최소 신장 트리(MST)는 모든 정점을 사이클 없이, 가능한 가장 작은 총 가중치로 연결하는 간선의 부분집합입니다. 정점이
V개일 때 간선은 정확히 V - 1개입니다.크루스칼 알고리즘과 프림 알고리즘의 차이는 무엇인가요?
둘 다 최소 신장 트리를 탐욕적으로 만듭니다. 크루스칼은 모든 간선을 전역으로 정렬한 뒤 union-find를 사용해 사이클을 만들지 않는 가장 저렴한 간선을 추가합니다. 프림은 시작 정점에서 하나의 트리를 바깥으로 키우며, 항상 트리를 벗어나는 가장 저렴한 간선을 추가합니다. 크루스칼은 희소 그래프에, 프림(힙 사용)은 밀집 그래프에 적합합니다.
크루스칼 알고리즘은 왜 union-find를 사용하나요?
간선을 추가하기 전에 크루스칼은 두 끝점이 이미 연결되어 있는지 확인해야 합니다. 그런 간선을 추가하면 사이클이 생기기 때문입니다. union-find(서로소 집합)는 "같은 컴포넌트에 있는가?"에 답하고 거의 상수 상각 시간에 컴포넌트를 합쳐, 알고리즘을 효율적으로 유지합니다.
프림 대신 크루스칼 알고리즘을 언제 써야 하나요?
그래프가 희소하고 모든 간선을 정렬 가능한 목록으로 이미 가지고 있다면 크루스칼을 택하세요.
E가 작으면 O(E log E) 정렬은 저렴합니다. 이진 힙이나 피보나치 힙을 쓰는 프림 알고리즘은 E가 V²에 가까운 밀집 그래프에서 유리한 경향이 있는데, 모든 간선을 미리 정렬하지 않아도 되기 때문입니다.크루스칼 알고리즘은 비연결 그래프에서도 동작하나요?
네. 그래프가 비연결이면 크루스칼은 단순히
V - 1개의 간선에 도달할 수 없고, 대신 최소 신장 숲(연결 컴포넌트마다 하나의 MST)을 만듭니다. union-find가 경로가 없는 정점끼리는 결코 합치지 않기 때문에 자연스럽게 나오는 결과입니다.크루스칼 알고리즘 구현 시 가장 흔한 실수는 무엇인가요?
union-find의 경로 압축과 랭크 기반 합치기를 생략하는 것으로, 각 연결 검사를 거의 상수에서 거의 선형으로 떨어뜨려 실행 시간을 지배할 수 있습니다. 또 다른 흔한 버그는 간선을 추가한 뒤 두 컴포넌트를 실제로 합치는 것을 잊는 것으로, 이후 간선이 사이클을 만들 수 있게 됩니다.
관련 자료
더 많은 시각화
