Randomized Algorithm - Boruvka’s MST Algorithm, Randomized MST

Boruvka’s MST Algorithm

• 프림, 크루스칼보다는 느리다.
• O(mlogm)

모든 노드는 가장 작은 인접엣지를 고른다.

가장 작은 인접엣지는 항상 MST에 들어간다.
a→b가 들어가지 않는다면 a→c→b와 같이 다른 엣지를 경유해서 들어온 것이 된다.
그러나 a→b 가 가장 작은 웨이트라면 그냥 a→c→b 대신에 a→c, a→b를 하면된다.
따라서 가장 작은 인접엣지는 항상 MST에 들어간다.

그러면 컴포넌트가 생긴다.

만약 두 노드가 고른 엣지가 겹치면, 전체 그래프는 분리되서 여러개의 컴포넌트가 생길 수도 있다.
최악의 경우 n/2 개 생긴다. (노드 2개씩은 무조건 연결되서 컴포넌트가 생기므로)

따라서 알고리즘을 그 상태로 다시 시도한다. (이부분 때문에 프림과 크루스칼보다 느리다.)
⇒ 연결된 트리가 만들어지면 그것이 MST이다.

---

Randomized MST

• O(n + m)

어려워서 이해하기를 포기