-
최소 신장 트리 알고리즘 (1): 크루스칼 알고리즘 (Kruskal's Algorithm)알고리즘 2025. 3. 11. 16:00
1. 크루스칼 알고리즘이란?
크루스칼 알고리즘(Kruskal's Algorithm)은 최소 신장 트리(MST: Minimum Spanning Tree)를 구하는 대표적인 알고리즘 중 하나이다. 그래프에서 모든 정점을 최소 비용으로 연결하는 트리를 생성하는 데 사용된다.
이 알고리즘은 간선을 오름차순으로 정렬한 후, 사이클을 형성하지 않는 선에서 가장 작은 가중치를 가진 간선을 선택하는 방식으로 동작한다. 유니온-파인드(Union-Find) 자료구조를 활용해 사이클 발생 여부를 효율적으로 판별한다.
1.1 크루스칼 알고리즘의 특징
- 탐욕적 접근법(Greedy Approach) 기반
- 무방향 가중 그래프에서 사용
- 사이클 방지를 위해 유니온-파인드 사용
- 시간 복잡도: O(E log E) (E는 간선 수)
2. 크루스칼 알고리즘의 동작 원리
크루스칼 알고리즘은 다음과 같은 단계로 수행된다:
- 간선 정렬: 모든 간선을 가중치 기준으로 오름차순 정렬
- 유니온-파인드 초기화: 각 정점을 독립된 집합으로 초기화
- 간선 선택:
- 가중치가 가장 작은 간선을 선택
- 선택한 간선이 사이클을 형성하지 않으면 트리에 추가
- 트리 완성: (V-1)개의 간선을 선택하면 종료 (V는 정점 수)
2.1 크루스칼 알고리즘 예제
다음과 같은 가중치 그래프에서 최소 신장 트리를 구하자:
(A) / | 1 3 (B) (C)-4-(D) \ | 2 5 (E)
2.2 크루스칼 알고리즘의 수행 과정
- 간선 정렬:
(A-B: 1) → (B-E: 2) → (A-C: 3) → (C-D: 4) → (C-E: 5)
- 간선 선택 및 트리 구성:
(A-B: 1) 선택 (B-E: 2) 선택 (A-C: 3) 선택 (C-D: 4) 선택
- 결과 MST:
(A) / | 1 3 (B) (C)-4-(D) \ 2 (E)
3. 크루스칼 알고리즘 구현 (Java)
import java.util.*; class Edge implements Comparable<Edge> { int src, dest, weight; public Edge(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } @Override public int compareTo(Edge other) { return this.weight - other.weight; } } public class Kruskal { static int findParent(int[] parent, int node) { if (parent[node] == node) return node; return parent[node] = findParent(parent, parent[node]); } static void union(int[] parent, int a, int b) { a = findParent(parent, a); b = findParent(parent, b); if (a != b) parent[b] = a; } public static void kruskal(List<Edge> edges, int V) { Collections.sort(edges); // 간선을 가중치 기준으로 정렬 int[] parent = new int[V]; for (int i = 0; i < V; i++) { parent[i] = i; } int mstWeight = 0; List<Edge> mst = new ArrayList<>(); for (Edge edge : edges) { if (findParent(parent, edge.src) != findParent(parent, edge.dest)) { mst.add(edge); mstWeight += edge.weight; union(parent, edge.src, edge.dest); } } System.out.println("MST의 총 가중치: " + mstWeight); for (Edge edge : mst) { System.out.println(edge.src + " - " + edge.dest + ": " + edge.weight); } } public static void main(String[] args) { List<Edge> edges = new ArrayList<>(); edges.add(new Edge(0, 1, 1)); edges.add(new Edge(1, 4, 2)); edges.add(new Edge(0, 2, 3)); edges.add(new Edge(2, 3, 4)); edges.add(new Edge(2, 4, 5)); int V = 5; // 정점 수 kruskal(edges, V); } }
4. 크루스칼 알고리즘의 성능 분석
4.1 시간 복잡도
- O(E log E): 간선 정렬 (우선순위 큐 사용 시)
- O(V + E): 유니온-파인드 (경로 압축 및 랭크 사용 시)
4.2 공간 복잡도
- O(V + E): 간선 리스트, 부모 배열
5. 크루스칼 알고리즘의 장점과 단점
5.1 장점
- 구현이 비교적 간단
- 희소 그래프(Sparse Graph, 간선의 수가 정점의 수에 비해 상대적으로 적은 그래프 (E ≪ V²))에 적합
- 유니온-파인드를 통해 사이클 검사가 빠름
5.2 단점
- 밀집 그래프(Dense Graph, 간선의 수가 정점의 수에 비례하거나 매우 많은 그래프 (E ≈ V²))에서는 비효율적
- 간선 정렬로 인한 추가 메모리 사용
6. 크루스칼 알고리즘의 활용 사례
- 네트워크 최적화: 최소 비용으로 네트워크 연결
- 도로망 설계: 도로 건설 시 최소 비용 경로 계획
- 전기 회로: 최소 전선으로 회로 설계
7. 크루스칼 알고리즘 vs. 프림 알고리즘
특징크루스칼 알고리즘프림 알고리즘
시간 복잡도 O(E log E) O((V + E) log V) 구현 방식 간선 중심(E) 정점 중심(V) 적합한 그래프 희소 그래프 (간선 수가 적을 때) 밀집 그래프 (간선 수가 많을 때) 사이클 검사 유니온-파인드로 검사 방문한 노드로 검사 8. 결론
크루스칼 알고리즘은 간선을 기준으로 최소 신장 트리를 생성하는 강력한 알고리즘으로, 희소 그래프에 적합하며 다양한 분야에서 활용된다. 밀집 그래프에서는 프림 알고리즘이 더 적합할 수 있으므로 문제의 특성에 따라 적절한 알고리즘을 선택하는 것이 중요하다.
'알고리즘' 카테고리의 다른 글
그리디 알고리즘: 개념, 종류 및 성능 비교 (0) 2025.03.14 최소 신장 트리 알고리즘 (2): 프림 알고리즘 (Prim's Algorithm) (0) 2025.03.12 최단 경로 알고리즘 (3): 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) (0) 2025.03.10 최단 경로 알고리즘 (2): 벨만-포드 알고리즘 (Bellman-Ford Algorithm) (0) 2025.03.08 최단 경로 알고리즘 (1): 다익스트라 알고리즘 (Dijkstra's Algorithm) (0) 2025.03.07