최소 비용 신장 트리(MST), 크루스칼 알고리즘(Kruskal Algorithm) 정의

크루스칼 알고리즘 (Kruskal Algorithm) 정의

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘으로 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘 중 하나이다. 

 

최소 비용 신장 트리 (Minimum Spanning Tree) 는 무엇일까?

• 정점 N개를 가지는 그래프에서 (N-1)개의 간선을 연결해야한다.
• 연결한 간선의 가중치 합이 가장 최소가 되는 그래프
• 모든 정점이 연결되야하지만 싸이클이 되면 안된다.

 

A : 간선이 5개로 N-1개를 가져야하는 신장 트리 법칙에 어긋나고, [1, 3, 4] 정점에서 순환 싸이클을 돌고 있으므로 연결 그래프이다.

B : 간선이 4개로 N-1개를 가져야하는 신장 트리 법칙에 어긋나지않지만 가중치 값 (2 + 5+ 7 + 6) 으로 최소 비용 신장 트리가 아닌 신장 트리이다.

C : 간선이 4개이고 가중치 값 (1 + 2+ 3 + 4) 으로 최소 비용 신장 트리이다.

 

크루스칼 알고리즘 동작 원리

1. 그래프의 간선들을 가중치 기준 오름차순으로 정렬한다.

2. 정렬된 간선 리스트를 순서대로 선택해서 정점들을 연결한다.

3. 만약 간선의 두 정점 a, b가 이미 연결되어 있으면 스킵한다.

4. 위 과정을 반복해서 최소 비용의 간선들로 모든 정점을 연결한다.

 

크루스칼 알고리즘 과정

C 그래프가 되는 과정을 그림으로 살펴보겠습니다.

가장 작은 가중치를 가진 간선 (1, 2)을 선택한다. 

1번 정점의 부모는 1, 2번 정점의 부모는 2

두 개의 정점이 부모가 같지 않으므로 스패닝 트리에 추가하고 2번 정점의 부모를 1로 변경한다.

부모 1	부모 2	부모 3	부모 4	부모 5
1, 2	X	3	4	5

그 다음으로 작은 가중치를 가진 간선 (1, 3)을 선택한다.

1번 정점의 부모는 1, 3번 정점의 부모는 3

두 개의 정점이 부모가 같지 않으므로 스패닝 트리에 추가하고 3번 정점의 부모를 1로 변경한다.

부모 1	부모 2	부모 3	부모 4	부모 5
1, 2, 3	X	X	4	5

다음으로 작은 가중치를 가진 간선 (3, 5)을 선택한다.

3번의 정점의 부모는 1, 5번 정점의 부모는 3

두 개의 정점이 부모가 같지 않으므로 스패닝 트리에 추가하고 5번 정점의 부모를 1로 변경한다.

부모 1	부모 2	부모 3	부모 4	부모 5
1, 2, 3, 5	X	X	4	X

다음으로 작은 가중치를 가진 간선 (3, 4)을 선택한다.

4번 정점의 부모는 4, 3번 정점의 부모는 1

두 개의 정점이 부모가 같지 않으므로 스패닝 트리에 추가하고 4번 정점의 부모를 1로 변경한다.

부모 1	부모 2	부모 3	부모 4	부모 5
1, 2, 3, 4, 5	X	X	X	X

선택한 간선의 개수가 정점(N)-1 이 되었으므로 간선 선택을 종료한다.

 

위 과정에서는 두 개의 정점이 부모가 같지 않은 경우가 존재하지 않으므로 간선을 선택하지 않은 경우가 없었지만 만약 부모가 같은 경우가 생기면 해당 간선을 선택하지 않고 넘어가면 된다.

 

간선을 선택하지 않고 넘어가는 경우

 

위 그림과 같은 경우가 두 개의 정점이 부모가 같은 경우에 해당된다. 

1번 정점의 부모는 1, 4번 정점의 부모는 1 

두 개의 정점이 부모가 같으므로 순환 싸이클이 발생한다. 즉, 해당 간선은 무시하고 넘어간다.

 

 

<크루스칼 알고리즘 코드>

package BOJ;

import java.io.*;
import java.util.*;

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, 1}, {1, 3, 2}, {1, 4, 4}, {3, 4, 3}, {3, 5, 5}, {4, 5, 7}, {2, 5, 6}};
        
        int[] parent = new int[6]; 
        int sum = 0; 
 
        for (int i=0; i<parent.length; i++) {
            parent[i] = i;
        }
        
        Arrays.sort(graph, new Comparator<int[]>() {
            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])) {
                sum += graph[i][2];
                union(parent, graph[i][0], graph[i][1]);
            }
        }
        
        System.out.println(sum);
    }
}