43. boruvka's mst algorithm [15 2주차]

43. Boruvka's MST Algorithm [15-2주차]

2024년 1월 14일 일요일

오후 5:49

<Boruvka's MST Algorithm>

O(mlogn) 시간이 걸림. 그러나 실제로는 Prim이나 Kruskal보다 느리다.

먼저, 각각의 노드에 대해 자신에게 붙어 있는 가장 작은 간선을 선택한다. 이 간선들은 무조건 MST에 포함되므로, MST에 넣는다.

증명

• 노드 u에 연결된 가장 가중치가 작은 간선이 (u, v)라 하자. MST에 (u, v)가 들어가지 않는다고 가정하고, MST에서 u와 v를 잇는 경로를 p라 한다. 이때, MST에서 u와 연결된 p내의 간선을 빼고 간선(u, v)를 추가하면, 모든 노드가 연결된 상태가 유지되면서 가중치는 줄어든다. 이는 MST라는 가정에 모순이므로, MST에는 (u, v)가 들어가야만 한다.

한 번 해서는 간선이 중복으로 선택되는 경우도 있기에 MST가 만들어지지 않을 수 있다. 따라서 하나의 연결 요소를 노드 하나로 축소한 그래프를 만들어, 그 그래프에 대해 알고리즘을 반복한다. 전체가 하나의 노드로 축소될 때까지 반복한다.

최악의 경우에도 한 번에 노드 개수가 절반씩은 줄어드므로 최대 logn번 반복하게 된다. 따라서 총 O(mlogn) 시간이 걸린다.

<Randomized MST>

Boruvka 라운드를 3번 돌린다. C를 Boruvka에서 선택된 간선의 집합이라 하자.

G가 축소되어 G'이 되었다. G'에서 각각의 간선을 50%확률로 선택하여 G''을 만든다.

G''에 전체 알고리즘을 재귀적으로 수행하면 Minimun Spanning Forest가 형성된다. (MSF는 MST에서 간선이 몇 개 빠진 것). 이를 F라고 하자.

F-Heavy Edges를 G'에서 제거한다. 이를 G'''이라 하자.

G'''에 위의 알고리즘 전체를 재귀적으로 수행하여 MST C'을 찾는다.

답은 C U C'이다.

Heavy Edge

그래프 내에 어떤 트리가 존재하고, 노드 a, b를 연결하는 간선(a, b)가 그 트리에 포함되지 않는다. a와 b를 연결하는 트리 내의 경로의 간선들 중 가중치 최대값이 m일 때, (a, b)의 가중치가 m보다 크면 (a, b)를 Heavy Edge 라 한다.

(a와 b의 트리 내 경로를 찾는 데 LCA가 사용된다)

수행 시간 T(n, m)은 다음과 같이 계산된다.

마스터 정리에 의해, T(n, m) = O(n+m) 이다.

두 번째 재귀에서 간선 개수가 1/4배가 되는 이유는, 대부분의 간선이 Heavy Edge가 되어 제거되기 때문이다.