크루스칼(Kruskal) 알고리즘 (with. 백준 1197번 최소 스패닝 트리)

 

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

크루스칼 알고리즘(Kruskal Algorithm)이란 최소 신장 트리(Minimum Spanning Tree)를 찾기 위해 사용되는 알고리즘이다.

 

신장 트리(Spanning Tree)
그래프 내의 모든 정점을 포함하는 트리

 

최소 신장 트리(Minimum Spanning Tree)
신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리

 

 

 

최소 신장 트리를 찾기 위해 모든 간선을 가중치에 따라 오름차순으로 정렬하는 아이디어를 사용하여 효과적으로 MST를 구할 수 있게 된다.

세부적인 구현 방법은 다음과 같다.

 

1. 모든 간선을 가중치에 따라 오름차순 정렬한다.

2. 간선을 하나씩 선택하여 사이클이 생기지 않을 때 연결하여 모든 노드가 연결될 때 까지 반복한다.

 

여기서, 사이클의 생성 여부와 노드의 연결은 Union-Find를 통해 수행된다.

사이클의 생성 여부를 Find를 통해 확인하여 연결이 가능한 상태라면 Union을 수행하는 것이다.

 

 

 

예제를 통한 이해

이해를 돕기 위해 실제 P.S. 예제인 백준의 최소 스패닝 트리 문제로 차근차근 알아가보자.

 

 

 

 

입력 첫 줄에 정점(Vertex)과 간선(Edge)이 주어지고, 간선에 대한 정보들이 주어진다.

각 간선에 대한 정보에는 A와 B의 정점이 가중치가 C인 간선으로 연결되어 있다고 한다.

 

예제 데이터는 위키 백과의 크루스칼 알고리즘 글에서 발췌해서 사용했다.

 

출처: 위키백과 크루스칼 알고리즘

 

위 그래프의 간선들의 정보를 저장하면 다음과 같다. (편의상 A = 1, B = 2와 같이 표현했다.)

 

 

모든 간선의 정보를, 간선을 기준으로 오름차순 정렬하여 하나하나 연결하면 된다.

최소 가중치에 대한 보장은, 이미 오름차순 정렬을 통해 연결되는 간선이 최소 가중치라고 보장받을 수 있게 된다.

또한 위에서 말한 것 처럼 Union-Find를 사용하여 사이클의 여부를 파악하고 연결을 수행하면 되겠다.

 

하나하나 연결해보자.

 

 

 

이제 다음 상황인 2와 5의 연결에서 2의 부모 노드는 1이고 5의 부모 노드는 3이다.

부모 노드가 다름은 곧 연결이 되지 않았음을 의미하기 때문에 Union을 진행한다.

Union 과정에서 5번 노드의 부모 노드가 바뀌는 것이 아니라, 각 노드의 부모 노드인 1, 3번 노드의 연결을 내부적으로 수행하게 된다.

 

위 그림처럼 5번 노드의 부모 노드가 변경되는 것이 아닌, 3번 노드의 부모 노드가 변경된다.

 

 

 

이제 2번 노드와 3번 노드의 차례인데, 이미 같은 부모 노드를 가지고 있다.

위에서 언급한 사이클이라는 것이 바로 이런 경우를 말하는데, 같은 부모 노드를 가질 경우 사이클이 존재한다고 판단한다.

즉, 최소 신장 트리를 구해야 하기 때문에 굳이 추가로 연결하지 않는다.

 

 

 

 

5번과 6번 노드를 확인할 때도 마찬가지다.

5번 노드의 부모 노드를 따라가보면, 5 -> 3 -> 1번 노드가 나오고, 6번 노드 또한 1번 노드이다.

재귀적으로 부모 노드를 탐색하여 결국 5번 노드의 부모 노드는 1번 노드가 되고 부모 노드가 같기 때문에 Union은 진행하지 않는다.

 

 

 

 

 

이와 같은 방식으로, 계속해서 사이클 여부를 판단하여 연결을 진행해준다.

 

 

 

 

시간 복잡도

Union-Find 알고리즘의 시간 복잡도가 상수이기 때문에, 정렬을 수행하는 데 걸리는 시간이 곧 크루스칼 알고리즘의 시간복잡도가 된다.

일반적으로, 정점과 간선이 주어질 때 O(ElogV)의 시간복잡도를 가진다.

 

 

 

 

구현 코드(with Java, 백준 1197번)

위의 백준 1197번을 한 번 풀어보자.

위에서 언급했던 것 처럼, 구현 방법은 정렬 -> 사이클 파악 여부에 따른 연결로 진행된다.

 

 

입력받은 정보를 바탕으로 간선의 가중치를 기준으로 오름차순 정렬한다.

int[][] graph = new int[E][3];

for (int i = 0; i < E; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int v1 = Integer.parseInt(st.nextToken());
    int v2 = Integer.parseInt(st.nextToken());
    int edge = Integer.parseInt(st.nextToken());
    graph[i][0] = v1;
    graph[i][1] = v2;
    graph[i][2] = edge;
}

Arrays.sort(graph, (o1, o2) -> o1[2] - o2[2]);

 

 

 

사이클이 존재하지 않는 경우(부모 노드가 서로 다를 경우) 연결한다.

int mstCost = 0;

for (int i = 0; i < E; i ++)  {
    int v1 = graph[i][0];
    int v2 = graph[i][1];
    if (find(parent, v1) != find(parent, v2)) {
        union(parent, v1, v2);
        mstCost += graph[i][2];
    }
}

 

 

 

전체 코드는 아래와 같다.

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        int[][] graph = new int[E][3];

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int edge = Integer.parseInt(st.nextToken());
            graph[i][0] = v1;
            graph[i][1] = v2;
            graph[i][2] = edge;
        }
        
        int[] parent = new int[V + 1];

        for (int i = 1; i <= V; i ++) {
            parent[i] = i;
        }
        
        Arrays.sort(graph, (o1, o2) -> o1[2] - o2[2]);
        int mstCost = 0;

        for (int i = 0; i < E; i ++)  {
            int v1 = graph[i][0];
            int v2 = graph[i][1];
            if (find(parent, v1) != find(parent, v2)) {
                union(parent, v1, v2);
                mstCost += graph[i][2];
            }
        }

        bw.write(String.valueOf(mstCost));
        bw.flush();
        bw.close();
    }

    private static int find(int[] parent, int x) {
        if (parent[x] == x) {
            return x;
        }

        return parent[x] = find(parent, parent[x]);
    }

    private static void union(int[] parent, int x, int y) {
        x = find(parent, x);
        y = find(parent, y);

        if (x == y) return;
        
        if (x < y) {
            parent[y] = x;
        }
        else parent[x] = y;
    }
}