Kruskal’s Algorithm
크루스칼 알고리즘은
그래프에서 얻을 수 있는 최소신장트리를 구하는 알고리즘이다.
이 알고리즘은 그리디 알고리즘에 기반한다.
최소신장트리
Minimum Cost Spanning Tree 라고 한다.
신장 트리, Spanning Tree 는
최소한의 엣지로 그래프의 모든 버텍스를 연결한다.
따라서 n개의 버텍스가 있다면 n-1 개의 엣지가 필요하다.
이걸 우리는 한 번 만들어보았는데,
강한 연결 요소, 이중 연결 요소를 구하면서 그렸던 DFS 스패닝 트리가
바로 이 신장 트리의 일종이다.
이 신장 트리는
그래프가 연결되어있어야 한다.
또한 우리가 지금 구하려는 최소 신장 트리는
이름에서도 알 수 있듯이
그 트리 엣지의 가중치의 합이 최소가 되게 하는 트리이다.
물론 이땐 그래프가 weighted graph 여야 한다.
이 트리엔 새로운 엣지가 없고
버텍스가 n 개 일 때 엣지는 n-1개이며
사이클이 없다.
그리디 알고리즘의 도입
-
해 (solution)
그래프에서 버텍스를 다 이으면서 그려지는 트리 (subgraph) 는 많다.
단, 제약 조건으로 이 중 n-1 개의 엣지를 쓰는 걸 스패닝 트리라고 하기로 한다. -
실제 가능한 해 (feasible solution)
1번에서 구한 해 중 제약 조건에 걸리지 않은 이들이다.
이들은 이미 스패닝 트리라고 부를 수 있다. -
목적 함수 도입 (objective function)
우리의 목적은 가중치의 합을 최소화하는 것이다. -
최적의 해 (optimal solution)
버텍스를 다 이으면서
n-1개의 엣지만 사용하고
가중치 합이 최소가 되는
최소 신장 트리를 얻을 수 있다.
크루스칼 알고리즘 (Kruskal’s Algorithm)
- 엣지들을 가중치의 오름차순으로 정렬한다.
- 그 엣지 중 하나 꺼내서, 트리에 추가했을 때 사이클 형성이 안 된다면, 트리에 추가한다.
- 트리 엣지가 n-1개 될 때까지, 혹은 리스트가 빌 때까지 반복한다.
여기서 리스트가 비었는데 트리 엣지가 n-1개가 아니면
connected graph 가 아니다.
2번에서 사이클 형성을 확인하는 이유?
A-B, B-C, C-A 의 A-B-C 사이클이 있다고 가정하자.
이 셋 중 하나는 필요가 없다.
하나를 지워도 돌아가면 되기 때문이다.
사이클이 생겼다는 건, 그 중 불필요한 엣지가 하나 이상 있다는 뜻인데
우리의 목적은 가중치의 최소화이므로
사이클이 있으면 안 된다.
성능 분석
E를 엣지의 수, V를 버텍스의 수라 하자.
알고리즘의 1번 과정에서 엣지를 정렬한다. O(ElogE)
2번 과정에서 사이클을 확인하는데 O(V) 가 걸릴 것이다.
3번에서 추가하는데도 O(V) 가 걸릴 것이다.
따라서 시간 복잡도는
O(V^2) 이거나 O(ElogE) 이다.
이때 그래프가 희소 그래프이면서 인접 리스트로 구현이 됐다면
O(ElogE) 보다는 O(V^2) 가 커질 것이므로
전체 시간 복잡도는 O(V^2) 가 된다.
반대로 그래프가 완전 그래프거나 행렬로 구현이 됐다면
엣지 수가 엄청 늘어나므로 O(ElogE) 가 커져서
시간 복잡도는 O(ElogE) 가 된다.
성능
반면 사이클을 수정하는 방법을 UNION-FIND 방식으로 구현할 수가 있다.
버텍스들에 라벨을 부여해서 UNION-FIND 방식으로 찾자.
UNION 방식으로 한다면 O(1) 이 걸릴 것이고, (매번 할 때마다 상수개이므로)
FIND 방식으로 한다면 O(logn)이 걸릴 것이다.
버텍스마다 라벨을 붙인 후에
엣지를 추가하려고 봤더니 그 버텍스의 라벨이 연결하려는 버텍스의 라벨과 같다면
이는 사이클이 형성된 것이다.
코드
자세한 것은 코드를 확인하자.
이 코드는 버텍스를 라벨링 하는
UNION 방식으로 구현되었으며
라벨링으로 사이클 확인 과정을 줄여서
추가하는 과정이 O(V)가 되었다.
E = V - 1 이라면 알고리즘을 쓸 필요가 없이 그래프 자체가 최소 신장 트리이며, (예외처리 필요)
E < V - 1 이라면 스패닝 트리를 그릴 수가 없다. (역시 예외처리 필요)
따라서 V <= E 이기 때문에
O(V)는 O(ElogE)이다.
시간 복잡도는 O(ElogE)이다.