[java] 자바로 크루스칼 알고리즘 구현하기

15 Dec 2023

java

크루스칼 알고리즘은 그래프에서 최소 비용 신장 트리를 찾는 알고리즘입니다. 이 알고리즘은 기본적으로 최소 비용 간선을 먼저 선택하고, 사이클을 형성하는 간선은 제외하는 방식으로 동작합니다.

알고리즘 구현

import java.util.*;

class Edge implements Comparable<Edge>{
    int start, end, weight;

    public Edge(int start, int end, int weight){
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge edge) {
        return this.weight - edge.weight;
    }
}

public class KruskalAlgorithm {
    private static int[] parent;

    public static int findParent(int x){
        if (x == parent[x]) return x;
        return parent[x] = findParent(parent[x]);
    }

    public static void unionParent(int a, int b){
        a = findParent(a);
        b = findParent(b);
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }

    public static void main(String[] args) {
        int v = 7; // 정점의 개수
        int e = 9; // 간선의 개수
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(1, 2, 29));
        edges.add(new Edge(1, 5, 75));
        edges.add(new Edge(2, 3, 35));
        edges.add(new Edge(2, 6, 34));
        edges.add(new Edge(3, 4, 7));
        edges.add(new Edge(4, 6, 23));
        edges.add(new Edge(4, 7, 13));
        edges.add(new Edge(5, 6, 53));
        edges.add(new Edge(6, 7, 25));

        parent = new int[v+1];
        for (int i = 1; i <= v; i++){
            parent[i] = i;
        }

        // 간선을 비용 기준으로 오름차순 정렬
        Collections.sort(edges);

        int totalWeight = 0;
        for (Edge edge : edges){
            if (findParent(edge.start) != findParent(edge.end)){
                unionParent(edge.start, edge.end);
                totalWeight += edge.weight;
            }
        }
        System.out.println("최소 비용 신장 트리의 길이: " + totalWeight);
    }
}

이 코드는 Union-Find 자료구조를 활용하여 크루스칼 알고리즘을 구현한 예시입니다. 주어진 간선들을 가중치 별로 오름차순으로 정렬한 뒤, 사이클을 형성하지 않는 경우에만 최소 비용 신장 트리에 포함시킵니다.

위의 예시 코드는 7개의 정점과 9개의 간선을 가진 그래프를 대상으로 크루스칼 알고리즘을 실행한 결과를 출력하는 형태로 작성되어 있습니다.

결론

크루스칼 알고리즘은 간선의 개수에 비례하는 시간복잡도를 가지며, 무방향 그래프에서 최소 비용 신장 트리를 찾는 데 효과적으로 활용될 수 있습니다. 위의 예시 코드를 참고하여 자신만의 그래프와 간선을 구성하여 알고리즘을 실행해 보시기 바랍니다.

알고리즘 구현

결론

참고 자료