[Kruskal] 크루스칼 최소신장트리

목표

모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

• 최적 해답? Kruskal MST 알고리즘에서 최적 해답은 MST로 구현됩니다. Minimum Spanning Tree의 약어로 여기에서 자세한 내용을 확인하세요.

아이디어

탐욕적인 방법(greedy method)을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 노드들을 최소 비용으로 연결합니다.

• 탐욕적인 방법?

결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것입니다. 탐욕적인 방법은 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야 합니다. 다행히 Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있습니다.

알고리즘

kruskal-1

kruskal-2

1. 모든 간선들을 가중치가 작은 순서대로 정렬한다.
2. 가장 작은 가중치를 사용해서 MST를 구하는 것이 싸이클을 만드는 것인지 확인한다.
3. 싸이클을 만든다면 해당 에지를 선택하지 않는다. 만들지 않는다면 MST를 구성하는데 사용한다.
4. 모든 노드가 연결되어 MST가 완성되면 종료한다.

싸이클을 구성하는지 확인하는 방법은 Union-find 알고리즘을 사용합니다.

시간복잡도

Union-find 알고리즘을 사용해서 Kruskal MST 알고리즘을 구현한다면 시간복잡도가 큰 연산은 두 가지가 있습니다.

1. 모든 간선의 가중치를 오름차순으로 정렬하는데 $O(ElogE)$
2. 싸이클을 판단할 때 Union-find 알고리즘에서 find()함수의 $O(logN)$

일반적으로 노드보다 에지가 많기 때문에 1번의 시간복잡도를 따른다고 할 수 있습니다.

특징

그래프에서 간선의 수가 적은 경우에 MST를 구현하는 것은 Kruskal 알고리즘이 적절하고, 많은 경우에는 Prim 알고리즘이 적합합니다.

참조

1. gmlwjd9405.github.io