[알고리즘] Kruskal 알고리즘 (feat. Union-Find)

Kruskal 알고리즘이란?

MST(최소신장트리)를 찾는 알고리즘 중 하나입니다. MST란 모든 노드를 사이클 없이 연결하는 신장 트리 중, 비용을 최소로 하는 트리입니다.

MST를 찾는 알고리즘은 Kruskal과 Prim 알고리즘이 있으며, dense graphs인 경우에는 Prim이, 그렇지 않은 경우에는 Kruskal이 빠르다고 하니, 상황에 맞게 선택하면 될 것 같습니다.

참고 : https://www.geeksforgeeks.org/difference-between-prims-and-kruskals-algorithm-for-mst/

Difference between Prim's and Kruskal's algorithm for MST - GeeksforGeeks

 

알고리즘 동작 방식

기본적으로 그리디하게 동작합니다. 사이클이 발생하지 않는 선에서 가장 값싼 간선부터 선택합니다.

1. 모든 간선 정보를 weight를 기준으로 오름 차순 정렬한다.

2. 간선을 선택한다.

3. 해당 간선을 선택했을 때, 사이클이 발생하는지 확인한다.

   (사이클이 발생하면, MST가 될 수 없기 때문에)

4. 사이클이 발생하면 다음 간선으로 넘어간다.

5. 사이클이 발생하지 않으면, 해당 간선을 선택한다.

6. 노드의 개수 - 1개만큼의 간선을 선택할 때까지 2 - 5번을 반복한다.

 

 

Union-Find 알고리즘

이때 사이클이 발생하는지 여부는 Union - Find 알고리즘으로 판단합니다. 이 알고리즘은 합집합 또는 서로소 집합이라고 불립니다.

 

이 알고리즘은 '부모 노드'를 기준으로 동작합니다.

 

우선 모든 노드의 부모 노드를 기록하는 배열을 생성하고, 초기 값으로 자기 자신을 생성합니다.

 

이후 두 노드를 연결하게 되면, 부모 노드가 작은 쪽을 기준으로(큰 쪽으로 해도 상관 없지만, 주로 작은 쪽으로 합니다) 부모 배열을 변경합니다.

 

예를 들어 1번과 2번 노드를 연결하면 아래와 같은 식이 됩니다.

[1, 2, 3, ...] -> [1, 1, 3, ...] 

이후 2번과 3번 노드를 연결하면 [1, 1, 1, ...] 이 될 것이고, 2번과 3번 노드의 부모 노드 같기 때문에 같은 집합임을 알 수 있습니다.

 

이 알고리즘은 크게 세 가지 기능으로 이뤄집니다.

1. getParent

해당 노드가 연결된 최상단 부모 노드를 재귀적으로 찾는 것입니다.

function getParent(노드, 부모 배열) {

    if (부모 배열[ 노드 ] == 노드) 

        return 노드;

    else

        return getParent(부모배열[노드], 부모배열])

}

 

2. FindUnion

두 노드가 같은 집합 안에 있는지 확인하는 기능입니다. 두 노드의 부모를 비교합니다.

Funtion findUnion(노드A, 노드B, 부모 배열) {

    부모A = getParent(노드A, 부모 배열)

    부모B = getParent(노드B, 부모 배열)

    if (부모A == 부모B)

        return 같은 집합;

    else

        reutrn 다른 집합;

}

 

3. Union

두 노드를 같은 집합으로 합치는 기능입니다.

두 노드의 부모 노드를 각각 구한 뒤, 더 큰 부모 노드를 작은 부모 노드로 바꾸는 것으로 표현할 수 있습니다.

Function  union(노드A, 노드B, 부모 배열) {

    부모A = getParent(노드A, 부모 배열)

    부모B = getParent(노드B, 부모 배열)

    if (부모A < 부모B)

        부모 배열[부모B] = 부모A

    else

        부모 배열[부모A] = 부모B

}