Kruskal algorithm

Krsukal algorithm은 MST(Minimum Spanning Tree)를 구하는 알고리즘이다.

Minimum Spanning Tree

어떠한 Graph가 Spanning Tree가 되려면 조건이 3가지가 필요하다.

1. Acyclic

2. 모든 점이 포함되어야 한다.

3. connected해야 한다.

이러한 조건을 만족하는 모든 Spanning Tree 중에 weight가 minimum한 것을 MST라고 한다.

물론 이 MST는 unique하지 않을 수 있다.

Cut Property

우선 cut이라는 것은 2개의 set(non-empty)로 나누는 vertex들의 partition을 의미한다.

그리고 crossing edge라는 것은 cut으로 인해 나누어진 하나의 set에서 다른 하나의 set으로 연결하는 edge를 crossing edge라고 한다.

이 때, 임의의 cut에 대해서 minimum weight의 crossing edge는 항상 MST에 속한다는 것이 cut property이다.

이 cut property는 MST의 다양한 알고리즘을 설명할 때, 중요한 역할을 한다.

Kruskal Algorithm

기본적인 개념은 weight를 오름차순으로 나열했을 때, 가장 작은 weight의 edge부터 고려한다.

이 edge의 양 끝점이 연결되어있지 않으면, 그 edge를 MST의 edge로 택한다.

이 작업을 선택한 edge 수가 V-1가 될 때 까지 반복하면 MST를 구할 수 있다.

이 때, edge의 양 끝점이 연결되어있는지를 판단할 때는 이전에 설명한 Union-Find를 이용하면 거의 상수시간 안에 판단할 수 있다.

시간복잡도

시간복잡도를 계산해 보면,

Edge를 오름차순으로 나열할 때, 우선 sort를 이용할 것이냐, PriorityQueue를 이용할 것이냐 부터 고민해야 한다.

sort는 기본적으로 ElogE만큼의 시간이 항상 걸리지만, PQ는 best case 때 delMin을 V-1번만 하면 된다.

그리고 코드가 내가 느끼기엔 더 예쁘게 느껴지므로, 나는 PQ를 더 선호한다.

그래서 PQ를 이용한다면, worst case때,

PQ build(E), PQ에서 최솟값을 뽑아내기(ElogE), union(Vlog*V) , connected(Elog*V) 만큼의 시간이 걸린다.

PQ를 build하는 데에는 bottom-up 방식을 이용하면 E만큼 걸리는데, java.util에 있는 PQ는 Collections만 constructor로 받는다.

그래서 실제로 해보니, 오히려 더 느리게 나오므로, 그냥 빈 PQ를 선언하고 모든 edge를 삽입해도 무리없다.

union는 V-1 만큼만 하면 되므로 O(Vlog*V)이고, connected는 worst때 모든 edge에 대해서 생각해야 하므로, O(Elog*V)이다.

주의사항

Kruskal Algorithm, Prim Algorithm 등 대부분의 우리가 배우는 MST 알고리즘은 모두 undirected graph 에서 적용되는 것들이다.

Directed MST는 Arborescence problem이라고 따로 분류 되므로 이건 나중에 배워보자.

Code