크루스칼 알고리즘 (with Javascript)

크루스칼 알고리즘이란?

크루스칼 알고리즘이란 그래프가 주어졌을 때 해당 그래프로 최소 신장 트리를 만드는 알고리즘이다.

그렇다면 최소 신장 트리란 무엇일까?

최소 신장 트리(MST, Minimum Spanning Tree)

우선 신장 트리(Spanning Tree)란 간선이 모든 정점에 연결되어 있고 순환하지 않는 그래프를 말한다.
연결되지 않은 정점이 있거나, 순환하는 부분이 하나라도 존재할 경우 신장 트리가 아니다.

'최소 신장 트리'는 간선의 비용의 합이 최소가 되도록 만든 신장 트리를 말한다.

위의 이미지 처럼 간선마다 비용이 존재하는 그래프가 주어졌을 때, 비용의 합이 최소가 되도록 신장 트리를 만드는 알고리즘이 크루스칼 알고리즘이고, 이렇게 만들어진 트리가 최소 신장 트리이다.

동작 방식

1. 간선을 비용을 기준으로 오름차순 정렬한다.
2. 정렬된 순서로 간선을 순회하며 사이클이 발생하는지 확인한다.
   • 사이클이 발생하지 않는 경우, 신장 트리에 포함시킨다.
   • 사이클이 발생하는 경우, 신장 트리에 포함하지 않는다.
3. 모든 간선을 순회하며 2번 과정을 반복한다.

그림으로 동작 방식을 살펴보자

초기 그래프가 위의 이미지처럼 되어있다고 가정하고, 각 노드의 부모 노드에 대한 정보를 담을 테이블을 생성해준다.

비용을 기준으로 정렬이 수행되고 첫 번째 간선부터 탐색을 시작한다.

1번과 2번을 확인한다. 두 노드의 루트노드가 같지 않으므로(사이클이 발생하지 않으므로) 신장트리에 포함시킨다.

2번과 4번을 확인한다. 마찬가지로 루트노드가 같지 않으므로 신장트리에 포함시킨다.

3번과 4번을 확인한다. 루트노드가 같지 않으므로 신장트리에 포함시킨다.

1번과 3번을 확인한다. 1번의 루트노드(1)과 3번의 루트노드(4->2->1)가 동일하므로 이는 사이클이 발생한다는 뜻이다.
따라서 신장트리에 포함시키지 않는다.

이를 코드로 구현해보자.

코드

// 노드의 개수, 간선의 개수
const [v, e] = [4, 4];
// 모든 간선을 담는 배열 [cost,a,b]
const edges = [
    [29, 1, 2],
    [75, 1, 3],
    [34, 2, 4],
    [53, 3, 4],
];
// 간선의 비용을 기준으로 오름차순 정렬
edges.sort((a, b) => a[0] - b[0]);
// 부모 노드 테이블 초기화
const parent = Array(v + 1).fill(0);
// 부모 테이블에서, 부모를 자기 자신으로 초기화
for (let i = 1; i <= v; i++) {
    parent[i] = i;
}

let result = 0;

for (let [cost, a, b] of edges) {
    // 사이클이 발생하지 않는 경우
    if (find(parent, a) !== find(parent, b)) {
        union(parent, a, b);
        result += cost;
    }
}

// 최소 신장트리의 비용의 총 합 출력
console.log(result);

// 루트 노드를 찾는다.
function find(parent, x) {
    // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀 호출
    if (parent[x] !== x) parent[x] = find(parent, parent[x]);
    return parent[x];
}

// 신장트리에 포함시킨다.
function union(parent, a, b) {
    a = find(parent, a);
    b = find(parent, b);
    // 더 작은 번호를 부모 노드로
    if (a < b) parent[b] = a;
    else parent[a] = b;
}

주목해야할 점은 find() 함수와 union() 함수다.
간선을 모두 확인하며 a 정점과 b 정점의 루트노드가 같은지 확인한다.
이때 find() 함수를 통해 parents 배열을 참조하여 현재 노드와 부모 노드의 번호가 다르다면 find() 함수를 재귀 호출하여 루트 노드를 찾아낸다. 그렇게 a와 b의 루트 노드를 구하여 두 노드의 루트노드가 일치하다면 사이클이 발생하는 것이므로 무시하고, 일치하지 않다면 union() 함수를 통해 집합에 포함시킨다.

이때는 a와 b의 노드 번호를 비교하여 더 작은 노드가 부모 노드가 되도록 만들어준다.

시간 복잡도

크루스칼 알고리즘의 시간 복잡도는 $O(E\log E)$ 이다. E : 간선의 개수
이유는 크루스칼 알고리즘에서 가장 시간이 오래걸리는 부분은 간선을 비용에 따라 정렬하는 부분이고, 정렬 라이브러리의 시간 복잡도가 $O(N\log N)$이기 때문이다.

참고

• 이것이 코딩테스트다. (파이썬)
• 최소 신장 트리