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

최소 비용 신장 트리

 

크루스칼 알고리즘은 최소 비용 신장 트리를 찾는 알고리즘이다.

최소 비용 신장 트리(MST) 란?

 

• Minimum Spanning Tree의 약자로 '최소 연결 부분 그래프'를 의미한다.
• 정점 N개를 가지는 그래프에서 (N - 1)개의 간선을 연결해야 한다.
• 연결한 간선의 가중치 합이 가장 최소가 되는 그래프
• 모든 정점이 연결되어야 하나, 싸이클이 되면 안된다.

 

그림을 통해 이해해보자.

A : 간선이 6개이므로 정점 - 1개를 가져야 하는 신장트리 법칙에 위배되며, 그래프가 순환(싸이클)하고있으므로 연결그래프다.

 

B : 간선은 4개지만, 간선끼리의 가중치 값이 8 + 5 + 4 + 3 + 2 = 22이므로 최소 신장트리가 아닌 신장트리의 일부다.

 

C : 간선이 4개이며, 싸이클이 없고 모든 정점이 연결되어있으며 가중치가 최소값이므로 최소 신장트리다.

 

 

크루스칼 알고리즘 - 과정

 

최소 비용 신장 트리에 대한 개념을 어느 정도 숙지했으니 이제 본격적으로 크루스칼 알고리즘의 과정에 대해서 살펴보자. 

알고리즘의 동작 과정은 다음과 같다.

1. 간선의 가중치를 오름차순으로 정렬한다.
2. 정렬된 간선 중에서 순서대로(가중치가 낮은 순으로) 간선을 조회한다.
    2-1. 간선을 선택하게 될 때, 사이클이 형성된다면 다음 간선으로 넘어간다.
    2-2. 사이클이 형성되지 않는다면 해당 간선을 선택한다.
3. 정점의 개수가 N일때, N-1만큼 간선을 뽑았다면 반복문을 종료한다.

 

이때, 사이클이 형성되는 여부는 Union & Find 연산이 필요하다.

서로소 집합과 연산에 대해 모른다면 이 글을 먼저 읽고 오길 바란다.

https://born2bedeveloper.tistory.com/29

[JAVA] 서로소 집합(Disjoint Sets)과 연산(Union & Find)

 

부모를 찾는 과정을 그림을 통해 좀 더 쉽게 알아보자.

 

먼저, 가장 가중치가 작은 간선 (1, 4)을 선택한다. 

노드 1의 부모는 1

노드 4의 부모는 4

둘의 부모는 같지 않으므로 (사이클이 없음) 간선 선택.

 

1과 4는 Union으로 합친다.

노드 4의 부모는 1이 된다.

 

부모 1 : 원소 [1, 4]

부모 2 : 원소 2

부모 3 : 원소 3

부모 5 : 원소 5

 

 

 

그 다음으로 작은 간선 (3, 4)를 선택한다.

노드 3의 부모는 3

노드 4의 부모는 1

둘의 부모는 같지않으므로 간선 선택

 

3과 4는 Union으로 합친다.

노드 3의 부모는 1이 된다.

 

부모 1 : 원소 [1, 3, 4]

부모 2 : 원소 2        

부모 5 : 원소 5        

 

 

 

그 다음으로 간선 (3, 1)을 선택한다.

노드 3의 부모는 1

노드 1의 부모는 1

둘의 부모가 같으므로 사이클이 발생한다! (순환)

 

따라서 해당 간선은 고르지 않고 넘어간다.

 

 

부모 1 : 원소 [1, 3, 4]

부모 2 : 원소 2        

부모 5 : 원소 5

 

 

 

 

그 다음으로 간선 (2, 5)를 선택한다.

노드 2의 부모는 2

노드 5의 부모는 5

둘의 부모가 다르므로 간선을 선택한다.

 

2과 5는 Union으로 합친다.

노드 5의 부모는 2이 된다.

 

부모 1 : 원소 [1, 3, 4]

부모 2 : 원소 [2, 5]   

 

 

 

그 다음으로 간선 (3, 5)를 선택한다.

노드 3의 부모는 1

노드 5의 부모는 2

둘의 부모가 다르므로 간선을 선택한다.

 

3과 5는 Union으로 합친다.

노드 5와 2의 부모는 1이 된다.

 

부모 1 : 원소 [1, 2, 3, 4, 5]

 

뽑은 간선의 개수가 정점 N-1 개인 4개가 되었으므로 간선 선택을 종료한다.

 

 

 

이렇게 해서 최소 신장 트리를 찾을 수 있었다!

 

 

크루스칼 알고리즘 - 코드를 통한 풀이

 

이제 알고리즘 동작 과정을 코드로 풀어볼 차례다!

위에서 언급한대로 간선을 선택하면 해당 간선의 정점 두 개를 Union으로 합치고, 사이클 여부를 판단할 때는 두 정점의 parent가 일치하는지를 find 함수를 통해 찾으면 된다.

 

package com.company;


import java.util.Arrays;
import java.util.Comparator;

public class Main {

    public static void union(int[] parent, int a, int b) {
        int a_parent = find(parent, a);
        int b_parent = find(parent, b);

        if (a_parent < b_parent)
            parent[b_parent] = a_parent;
        else
            parent[a_parent] = b_parent;
    }

    public static int find(int[] parent, int i) {
    //자기 자신을 가리키니 부모가 맞다.
        if (parent[i] == i) 
            return i;
        return find(parent, parent[i]);
    }

    public static void main(String[] args) {
        int [][]graph = {{1, 2, 6}, {1, 3, 3}, {1, 4, 1}, {2, 5, 4}, {3, 4, 2}, {3, 5, 5}, {4, 5, 7}};
        // 1과 index1을 맞추기 위해 + 1
        int []parent = new int[6]; 
        //최소 신장트리의 가중치 총 합
        int total = 0; 

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
         // 가중치 기준으로 정렬
        Arrays.sort(graph, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });
        for (int i = 0; i < graph.length; i++) {
            if (find(parent, graph[i][0]) != find(parent, graph[i][1])) {
                total += graph[i][2];
                union(parent, graph[i][0], graph[i][1]);
            }
        }
        System.out.println("최소 비용 신장 트리 가중치의 합은 " + total);
    }
}

 

필자는 MST의 가중치를 구하도록 코드를 구현했다.

필요에 따라 변수를 따로 선언하여 MST를 이루는 간선을 따로 저장하여 MST를 출력하는 등 여러 방식으로 응용이 가능하니 기본만 안다면 목적에 맞게 변형하여 쓸 수 있을 것이다.