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

크루스칼 알고리즘을 사용하기 위해서는 union-find 알고리즘을 알아야 한다

2022.04.14 - [자료구조, 알고리즘] - Union-Find(합집합 찾기)알고리즘

Union-Find(합집합 찾기)알고리즘

- 신장 트리(Spanning tree)

: 그래프 내에 있는 모든 정점들을 포함하고, 정점들 간에 서로 연결되며 사이클을 이루지 않는 그래프이다

신장 트리는 정점의 개수가 n개일 때 간선의 개수가 n-1개이다.

이때 간선의 가중치들의 합이 최소가 되게 하는 신장 트리를 최소 신장 트리(Minimum Spanning Tree, MST)라고 한다.

 

- 크루스칼 알고리즘

: 최소 신장 트리를 구하기 위한 알고리즘으로 그리디 알고리즘의 일종이다.

1. 주어진 모든 간선의 가중치들을 비용이 낮은 것부터 오름 차순 정렬한다

2. 정렬된 순으로 간선들을 선택하며 간선의 양 끝 정점을 Union 한다. 이때 선택된 두 정점이 같은 부모를 가지고 있다면 사이클이 있다고 판단하여 Union 하지 않는다

 

소스 코드

/*
sample input(첫 줄의 첫 숫자는 정점의 개수, 두 번째 숫자는 간선의 개수).
6 9
1 6 5
2 4 6
1 2 7
3 5 15
2 3 3
4 5 7
 */
class Main {
    static int V, E;
    static int[][] graph;
    static int[] parent;
    static int final_cost;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        V = sc.nextInt();
        E = sc.nextInt();
        int n = 0;  //연결된 간선의 개수
        graph = new int[E][3];
        for (int i = 0; i < E; i++) {
            graph[i][0] = sc.nextInt();
            graph[i][1] = sc.nextInt();
            graph[i][2] = sc.nextInt();
        }
        parent = new int[V];
        final_cost = 0;

        //비용 순으로 오름차순 정렬
        Arrays.sort(graph, (o1, o2) -> Integer.compare(o1[2], o2[2]));

        //부모를 자기 자신으로 초기화
        for (int i = 0; i < V; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < E; i++) {
            if (n >= V - 1) break; //간선이 n-1개 연결되었다면 최소 신장 트리가 완성된 것이므로 끝
            if (find(graph[i][0]) != find(graph[i][1])) { //두 정점이 사이클을 이루지 않으면
                union(graph[i][0], graph[i][1]);
                final_cost += graph[i][2];
                n++;
            }
        }

    }

    public static int find(int x) {
        if (parent[x] == x) return x;
        else return find(parent[x]);
    }
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);

        if (x > y) parent[x] = y;
        else parent[y] = x;
    }
}

 

 

참고

[Java]크루스칼 알고리즘(Kruskal Algorithm) :: TH (tistory.com)

[Java]크루스칼 알고리즘(Kruskal Algorithm)