크루스칼 알고리즘(최소 신장 트리)

크루스칼 알고리즘은 그리디 알고리즘의 일종으로, 최소한의 비용으로 모든 정점을 연결하는 최소 신장 트리를 찾는 데 사용된다.

이 알고리즘은 간선들을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않으면서 간선을 추가하여 최소 신장 트리를 만들어 간다.

 

동작 순서

---

1. 초기화: 에지 리스트와 유니온-파인드가 필요하다.
2. 가중치 기준 정렬: 가중치가 작은 에지부터 연결을 시도하기 때문에 가중치를 기준으로 오름차순 정렬한다.
3. 연결 시도: 가중치가 작은 에지부터 순회하며 이미 연결된 정점이 아닌 정점들을 연결한다. 이 때 유니온-파인드 알고리즘이 필요하다.

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Kruskal {

    static void kruskalMST(int V, List<Edge> edges) {
        // 최소 신장 트리
        int minimumValue = 0;

        UnionFind unionFind = new UnionFind(V);

        PriorityQueue<Edge> q = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));
        q.addAll(edges);

        // 최단 경로는 V-1 를 넘을 수 없다.
        for (int i = 0; i < V - 1; i++) {
            Edge edge = q.poll();
            // 이미 연결되어 있다면 사이클이 발생한다.
            if (unionFind.find(edge.src) != unionFind.find(edge.dest)) {
                unionFind.union(edge.src, edge.dest);
                minimumValue += edge.weight;
            }
        }
        // 결과 출력
        System.out.println(minimumValue);
    }
}