[java] 크루스칼 알고리즘

04 Dec 2023

java

크루스칼(Kruskal) 알고리즘은 그래프의 최소 신장 트리(Minimum Spanning Tree)를 구하는 알고리즘 중 하나입니다. 최소 신장 트리란, 그래프에서 모든 노드를 연결하면서 모든 간선의 가중치의 합이 최소가 되는 트리입니다.

알고리즘 동작 과정

모든 간선을 가중치 오름차순으로 정렬합니다.
정렬된 간선을 순차적으로 검사하면서 사이클이 생성되지 않도록 간선을 선택합니다.
- 사이클 검사는 유니온 파인드(Union-Find) 알고리즘을 이용합니다. 간선의 양끝점이 같은 집합에 속하는지 확인해야 합니다.
- 양끝점이 다른 집합에 속해 있다면, 두 집합을 합치기 위해 간선을 선택합니다.
모든 간선에 대해 위의 과정을 반복하며, 선택한 간선들로 최소 신장 트리를 구성합니다.

예시 코드

import java.util.*;

class KruskalAlgorithm {
    private int[] parent;
    
    private int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }
    
    private void union(int x, int y) {
        x = find(x);
        y = find(y);
        
        if (x != y) {
            parent[y] = x;
        }
    }
    
    public List<Edge> kruskalAlgorithm(List<Edge> edges, int n) {
        parent = new int[n];
        List<Edge> mst = new ArrayList<>();
        
        // 모든 노드를 개별 집합으로 초기화
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        // 간선을 가중치 오름차순으로 정렬
        Collections.sort(edges, (a, b) -> a.weight - b.weight);
        
        // 정렬된 간선을 순차적으로 검사
        for (Edge edge : edges) {
            // 양끝점이 다른 집합에 속해있는지 확인
            if (find(edge.start) != find(edge.end)) {
                // 두 집합을 합치기 위해 간선을 선택
                union(edge.start, edge.end);
                mst.add(edge);
            }
        }
        
        return mst;
    }
    
    static class Edge {
        int start;
        int end;
        int weight;
        
        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }
}

위 코드는 크루스칼 알고리즘을 구현한 예시입니다. kruskalAlgorithm 메소드는 간선 리스트와 노드의 개수를 입력받아 최소 신장 트리를 구성하는 간선들의 리스트를 반환합니다.

참고 자료

Kruskal’s algorithm - Wikipedia
Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein