크루스칼 알고리즘 Kruskal’s Algorithm

 

 

 

이전 시간까지 Minimal Spanning Tree, 즉 MST를 구하는 기본적인 방법을 배워봤습니다.

이제부턴 Minimal Spanning Tree를 구하는 두 가지 방법 중 첫 번째 크루스칼 알고리즘을 배워볼겁니다. 

- Kruskal’s Algorithm (오늘 배울거)

- Prim’s Algorithm

 

정의

크루스칼 알고리즘은 결국 MST처럼 최소 비용의 경로를 찾는겁니다. 그전에 정의부터 설정하겠습니다.

그래프 G는 비방향 가중치 그래프입니다.

w : E→R

w는 가중치고 E는 그래프 G의 간선 집합입니다. R은 실수 집합입니다.

즉, w는 간선 집합 E의 각 간선에 대해 실수 값을 매핑하는 가중치 함수입니다. 

 

알고리즘은 각 정점이 자신의 컴포넌트로 시작합니다. 즉, 초기에는 모든 정점이 독립적으로 존재합니다.

알고리즘은 반복문을 돌려서 두 개의 컴포넌트를 선택하여 연결하는 Light edge를 선택하여 병합합니다. 

이 간선은 컷을 가로지르는 가장 작은 가중치의 간선입니다.

뜻이 뭔지 모르겠다면 저번 포스팅을 다시 보시면 됩니다.

https://kimyir.tistory.com/133

최소 신장 트리 Minimum Spanning Trees

 

간선 집합을 가중치에 따라 오름차순으로 스캔합니다. 즉, 가장 작은 가중치의 간선부터 선택합니다.

알고리즘은 불일치 집합(Disjoint Set) 자료구조를 사용하여 간선이 서로 다른 컴포넌트를 연결하는지 확인합니다. 

이를 통해 사이클을 방지합니다.

 

그럼 이를 통해 의사코드를 보시겠습니다.

 

의사코드

 

코드를 분석해봅시다.

A를 초기화 : O(1) -> MST 집합 A를 초기화하는 데 상수 시간이 소요됩니다.

첫 for 반복문 : |V| MAKE-SETs -> 각 정점에 대해 MAKE-SET을 호출하므로 O(|V|)의 시간이 소요됩니다.

E를 정렬 : O(E logE)  -> 간선 집합 E를 가중치에 따라 정렬하는 데 걸리는 시간입니다.
두 번째 for 반복문 : O(E) FIND-SETs and UNIONs -> 각 간선에 대해 FIND-SET과 UNION을 호출하므로 O(E)의 시간이 소요됩니다.

 

Find - SET과 Unions에 대해서 아래에서 설명드리겠습니다.

 

불일치 집합 데이터 구조

disjoint-set data structure, 즉 불일치 집합 자료구조를 사용하여 효율적으로 FIND-SET과 UNION을 수행합니다.

불일치 집합 자료구조(Disjoint Set Data Structure), 또는 유니온-파인드(Union-Find) 자료구조는 서로 겹치지 않는 집합을 효율적으로 관리하기 위한 자료구조입니다. 

 

Find : 특정 원소가 속한 집합의 대표 원소(루트)를 찾는 연산입니다. 이 연산은 경로 압축(Path Compression)을 통해 최적화할 수 있습니다.
Union : 두 개의 집합을 하나로 합치는 연산입니다. 이 연산은 union by rank 또는 union by size 기법을 사용하여 트리의 높이를 최소화합니다.

 

 

예시 

 

1. 의사 코드에 있던 과정처럼 초기화를 먼저합니다.

각 Vertex 별로 하나의 Component를 생성합니다. Disjoint-set |V|개를 생성합니다.
초기화하면 {a}, {b}, {c}, {d}, {e}, {f}, {g}, {h}, {i} 로 구성된 Set이 만들어집니다.

 

2. 간선의 가중치 오름차순으로 정렬합니다.

weight가 가장 작은 1부터 12까지 정렬합니다.

 

3. 간선 선택 후 Union 연산합니다.

가장 작은 가중치 1이었던 간선(c, f)를 먼저 선택합니다.

find(c)와 find(f)를 통해 두 정점이 연결되어 있지 않음을 확인합니다.
union(c, f)를 수행하여 집합을 합칩니다.
결과 집합: {a}, {b}, {c, f}, {d}, {e}, {g}, {h}, {i}

 

그 다음으로 작은 가중치인 2 간선(g, i)를 선택합니다.

find(g)와 find(i)를 통해 두 정점이 연결되어 있지 않음을 확인합니다.
union(g, i)를 수행하여 집합을 합칩니다.
결과 집합: {a}, {b}, {c, f}, {d}, {e}, {g, i}, {h}

 

그 다음으로 작은 가중치인 3 간선 (e, f)를 선택합니다.

find(e)와 find(f)를 통해 두 정점이 연결되어 있지 않음을 확인합니다.
union(e, f)를 수행하여 집합을 합칩니다.
결과 집합: {a}, {b}, {c, e, f}, {d}, {g, i}, {h}

 

이런 식으로 계속 진행하여 모든 정점이 연결될 때까지 반복합니다. 

각 단계에서 사이클이 형성되지 않도록 주의하며, 최종적으로 최소 신장 트리를 구성하게 됩니다.

 

크루스칼 알고리즘으로 결과적으로 생성된 MST 결과입니다.

 

시간 복잡도

크루스칼 알고리즘의 첫 번째 단계는 모든 간선을 가중치에 따라 정렬하는 것입니다.
이 단계의 시간 복잡도는 O(E log E)입니다. 

여기서 E는 간선의 수입니다. 정렬 알고리즘의 일반적인 시간 복잡도가 로그 시간 복잡도를 포함하기 때문입니다.

 

두 번째 단계는 각 간선을 선택할 때마다 find와 union 연산을 수행하는 것입니다.
이 연산의 시간 복잡도는 O(E α(V))입니다. 여기서 α는 아커만 함수의 역함수로, 매우 느리게 증가하는 함수입니다. 

사실상 이 값은 거의 상수에 가깝습니다.

이제 이 연산을 간선 뿐 아니라 정점에도 사용하면 정점 갯수만큼 더해준 값에 아커만 곱해주면 되겠죠?

따라서 정리해보면

O( (V + E) α(|V|) ) + O(E log E) 이 나오게 됩니다.

 

|E| ≤ |V|² : 간선의 수는 정점의 수의 제곱 이하입니다.

즉, 완전 그래프의 경우 모든 정점이 서로 연결되므로 최대 간선 수는 |V|²입니다.

|E|가 |V|² 이하이므로, 양변에 로그를 취하면 lg |E| ≤ lg (|V|²) = 2 lg |V|가 됩니다.

 lg |E|는 O(lg |V|)와 같고, 이는 O(lg E)로 표현할 수 있습니다.

 

|E| ≥ |V| − 1 : 간선을 다 연결하면 노드에서 1 빼주면 간선의 수가 나옵니다.

연결 그래프에서 |E|가 |V| - 1 이상이므로, 전체 시간 복잡도는 O(E α(V)) + O(E log E)로 표현됩니다.

O(Eα(|V|)) + O(E logE) 에서 아커만 함수는 거의 상우에 가깝기 때문에 생략해도 됩니다.
따라서, O(E log E): 전체 시간 복잡도는 간선의 수에 따라 로그 시간 복잡도를 가집니다.

 

하지만 위에서 말했듯이 log |E|는 O log|V|와 같다고 했죠?

그래서 O(E log V) 로 표현해도 맞긴합니다.

 

어쨋든 크루스칼 알고리즘의 실행 시간 시간 복잡도는 간선의 수에 따라

O ( E log E) 입니다.