[Update]
- 2024.04.11: [그리디 알고리즘] 크루스칼 알고리즘(Kruskal Algorithm)
크루스칼 알고리즘이란?
크루스칼 알고르짐은 주어진 그래프에서 모든 정점을 최소 비용으로 연결하는 최소 신장 트리를 찾는 데 사용된다. 그래프의 간선은 가중치가 할당되어 있으며 이 가중치의 합이 최소가 되도록 하면서 모든 정점을 연결하는 것을 목표로 하는 알고리즘이다.
크루스칼 알고리즘을 학습하기 전에, 신장 트리와 최소 신장트리에 대해 알아보자.
신장 트리와 최소 신장 트리
신장 트리란 그래프에서 모든 정점을 포함하여, 정점들 사이를 연결하되 사이클이 존재하지 않는 구조를 말한다. 따라서 정점의 개수가 N이라면, 간선의 개수는 N-1이 되어야 한다.
최소 신장 트리는 간선들의 가중치 합이 최소가 되도록 그래프의 일부 간선을 선택하여 만든 신장 트리를 말한다. 최소 신장 트리를 구하는 알고리즘 문제는 다양하다. 예를 들어, 여러 지점을 최소한의 간선으로 연결하는 네트워크 구축 문제나, 도로 시스템에서 모든 도시를 연결하되 도로 길이 합을 최소화 하는 문제 등이 그 예시이다.
크루스칼 알고리즘 구현
크루스칼 알고리즘은 최소 신장 트리를 구하는 그리디 알고리즘 중 하나이다. 이 알고리즘은 주어진 그래프에서 간선들의 가중치를 오름차순으로 정렬한 후, 사이클을 형성하지 않는 선에서 순차적으로 간선을 선택하여 최소 신장 트리를 만든다.
이 과정에서 사이클을 판별하기 위해 Union-Find 자료구조를 사용한다. Union-Find는 각 정점을 트리 형태로 표현하여 집합을 나타내며 각 정점의 부모를 통해 집합의 구조를 파악한다. 초기에는 각 정점이 자기 자신만을 포함하는 집합으로 설정한다.
가중치의 오름차순으로 정렬된 간선을 순차적으로 선택하면서 선택한 간선의 두 정점이 서로 다른 집합에 속해 있을 때만 해당 간선을 선택하고 두 정점을 하나의 집합으로 합친다. 이 때 사이클을 형성하는지 여부를 각 정점의 부모를 확인하여 판단한다. 만약 두 정점의 부모가 같다면 사이클이 형성되므로 해당 간선은 선택되지 않는다.
이 알고리즘은 간선의 가중치를 기반으로 최적해를 찾는 방식으로 동작하며, 일반적으로 시간 복잡도가 O(E logE)이다.
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;
}
// 가중치를 기준으로 정렬하기 위한 Comparable 구현
@Override
public int compareTo(Edge other) {
return this.weight - other.weight;
}
}
public class Kruskal {
private int V; // 정점의 개수
private List<Edge> edges; // 간선 리스트
public Kruskal(int V) {
this.V = V;
edges = new ArrayList<>();
}
// 간선 추가
public void addEdge(int src, int dest, int weight) {
edges.add(new Edge(src, dest, weight));
}
// Union-Find의 Find 연산
private int find(int[] parent, int i) {
if (parent[i] == i)
return i;
return find(parent, parent[i]);
}
// Union-Find의 Union 연산
private void union(int[] parent, int x, int y) {
int xRoot = find(parent, x);
int yRoot = find(parent, y);
parent[yRoot] = xRoot;
}
// 크루스칼 알고리즘 구현
public List<Edge> kruskalMST() {
List<Edge> MST = new ArrayList<>();
// 간선을 가중치로 정렬
Collections.sort(edges);
// 부모 배열 초기화
int[] parent = new int[V];
for (int i = 0; i < V; i++)
parent[i] = i;
int edgeCount = 0;
int index = 0;
while (edgeCount < V - 1 && index < edges.size()) {
Edge edge = edges.get(index++);
int x = find(parent, edge.src);
int y = find(parent, edge.dest);
// 사이클이 형성되지 않는 경우에만 간선을 선택하여 MST에 추가
if (x != y) {
MST.add(edge);
union(parent, x, y);
edgeCount++;
}
}
return MST;
}
// 예시 실행
public static void main(String[] args) {
int V = 4;
Kruskal graph = new Kruskal(V);
// 예시 그래프의 간선 추가
graph.addEdge(0, 1, 10);
graph.addEdge(0, 2, 6);
graph.addEdge(0, 3, 5);
graph.addEdge(1, 3, 15);
graph.addEdge(2, 3, 4);
// 크루스칼 알고리즘 수행 및 결과 출력
List<Edge> MST = graph.kruskalMST();
System.out.println("Minimum Spanning Tree:");
for (Edge edge : MST) {
System.out.println(edge.src + " - " + edge.dest + ": " + edge.weight);
}
}
}