이번 포스팅은 저번 Prim 알고리즘에 이어서 탐욕법을 사용해 mst를 구하는 Kruskal 알고리즘과 Boruvka 알고리즘을 학습한다.
Kruskal 알고리즘
Alg KruskalMST()
input simple connected weighted graph G
output MST
for each v in G.vertex() {
define Sack(v) <- {v}
}
Q <- priority queue cotaining all edges of G using weight as key
mst <- null
while(mst.edges() < n-1) {
u, v <- Q.remove()
if(Sack(u) != Sack(v)) {
mst.addEdge(u, v)
merge Sack(u) & Sack(v)
}
}
return mst크루스칼 알고리즘 역시 탐욕법에 기초한다.
크루스칼 알고리즘은 그래프 모든 정점에 대해 각각의 부분 집합을 생성한다. 여기서는 배낭을 의미하는 Sack()으로 정의했다. 그 다음 모든 간선들을 우선순위 큐에 저장한다. 우선순위는 최소 가중치가 된다.
반복문은 두 개의 다른 Sack()에서 양 끝점을 가진 가중치 간선을 mst에 포함하고 배낭을 merge한다. 각 반복에서 Q의 원소(간선)을 추출해 서로 다른 정점 u, v를 도출한다. u와 v가 같은 Sack()이 아니라면 해당 간선을 mst에 포함시킨 후 Sack(u)와 Sack(v)를 합친다.
Kruskal 알고리즘 그림 수행 예시
회색 영역은 Sack()을 의미한다. 각 정점들이 독자적인 Sack()을 가진 채로 알고리즘을 시작한다.
전체 간선 중 (A, B)가 제일 작기 때문에 mst에 (A, B) 간선을 추가하고 Sack(A)와 Sack(B)를 merge한다. 이후 (E, F) -> (D, F) -> (B, C) 순으로 알고리즘이 진행된다.
(A, C)는 가중치가 작지만 Sack(A)와 Sack(C)가 같기 때문에 걸러진다.
크루스칼 알고리즘은 어떠한 정점에 대해 인접 정점 정보를 사용하지 않고 모든 간선을 큐에 때려박고 간선 가중치가 작은 순서대로만 추가한다. 따라서, 단순하게 간선리스트로만으로 구현할 수 있다는 장점이 있다.
하지만, 어떤 정점 v가 속한 Sack(v)를 O(1)시간에 도출할 수 있게 해야하고 merge 작업에 대해 서로 다른 Sack() 중 비교적 작은 집합이 큰 집합에 merge될 수 있도록 하는 최적화 고민을 해볼 수 있다.
Kruskal 알고리즘 성능
우선순위 큐가 힙이라 가정한다면,
큐에 간선을 삽입하고 삭제하는데 O(Elog E) 걸린다. 여기서 그래프는 단순 그래프이므로 O(log E) = O(log V)이므로 O(Elog V)가 된다.
Sack()의 merge에 대해서는 O(min(Sack(u).size(), Sack(v).size())가 소요된다. 정점 원소가 새로운 Sack()으로 이동할 때마다 원래의 것보다 최소 2배 크기로 옮겨지므로 각 원소는 O(log V) 이동되고 전체 원소에 대해 O(Vlog V)다.
따라서, 크루스칼 알고리즘은 O(Elog V + Vlog V) 시간에 수행된다. 단순 연결 그래프에서 V = O(E)이므로 O(Elog V)로 단순화시킬 수 있다.
Boruvka 알고리즘
보루프카 알고리즘은 크루스칼 알고리즘과 유사하지만 우선순위 큐를 사용하지 않으며 한 번의 반복 라운드에서 mst에 많은 간선을 취하는 것이 특징적이다.
보루프카 알고리즘은 크루스칼 알고리즘과 같이 각 정점이 독자적인 Sack()을 갖고 출발한다. 그 다음 각 Sack()에서 간선이 가장 작은 놈들을 모든 Sack()에 대해서 찾는다. 이 때 찾는 간선들은 본인 Sack()과 다른 Sack()을 연결하는 것이어야 한다.
이렇게 알고리즘을 수행하면서 여러 Sack()을 한꺼번에 키워 나간다.
보루프카 알고리즘은 각 반복 라운드에서 서로의 Sack()을 교차하는 최소 가중치 간선을 찾기 위해 정점들의 인접 리스트를 전면 탐색한다. 모든 간선 (u, v)에 대해 2번 조사하기 때문에 O(E) 소요된다.
그렇다면 탐색의 반복은 몇 회일까. 각 라운드에서 Sack()으로부터 나오는 간선을 골라 다른 Sack()과 merge한다. 각 반복 라운드마다 Sack()의 총 개수는 최소 절반으로 줄어들기 때문에 총 라운드의 횟수는 O(log V)가 된다. 따라서, 보루프카 알고리즘 시간복잡도는 O(Elog V)다.
3가지 mst 알고리즘 비교
prim, kruskal, boruvka 모두 시간복잡도는 O(Elog V)이고 탐욕법에 기반한다. 하지만 각 알고리즘 구현을 위한 자료구조형이 조금씩은 다르다. prim은 우선순위 큐만 사용하지만 kruskal은 Sack()을 저장하기 위한 분리 집합도 사용한다. 마지막 boruvka는 Sack()을 쓰지만 우선순위 큐는 사용하지 않는다.
참고 : 국형준. 알고리즘 원리와 응용. 21세기사, 2018.
