[알고리즘] Sollin 알고리즘이란?
오늘은 마지막으로 MST를 찾는 알고리즘 중 Sollin 알고리즘에 대해서 알아보겠습니다.
Sollin 알고리즘이란?
Sollin 알고리즘도 Kruskal, Prim 알고리즘과 같이 하나의 그래프에서 MST를 찾는 알고리즘입니다.
Sollin은 각 정점을 하나의 트리로 간주하고, 각 트리 사이의 간선 중 가장 작은 간선을 선택하여 두 개의 트리를 하나로 이어주는 방식을 통하여 MST를 구성하는 방식입니다.
순차적으로 진행하는 Kruskal과 Prim과는 달리 한번에 진행하여 최악의 상황이 아닌 일반적인 상황에서는 굉장히 빠른 속도로 완료할 수 있다는 장점이 있습니다.
그럼 이제 그림을 통해서 확인해봅시다.
이런 그래프가 있습니다. Kruskal과 Prim에서 다뤘던 그래프와 동일합니다.
여기서 우리는 각 정점을 하나의 트리라고 생각하고 트리 사이를 잇는 가장 가까운 간선을 택하여 연결해줍니다.
0번 정점은 1번 정점과 가깝고, 1번 정점은 6번 정점과, 2번 정점은 5번 정점과
3번 정점은 5번 정점과 4번 정점은 6번 정점과, 6번 정점은 4번과 가까우므로 해당하는 정점끼리 묶어주면 아래와 같은 두 개의 트리가 만들어지게 됩니다.
이제 이 트리 두개를 이어주는 가장 가까운 간선을 택하면 됩니다. 2번 정점과 4번 정점을 잇는 가중치가 7인 간선이 채택되겠군요.
그러면 아래와 같은 MST가 생성됩니다.
역시나 Kruskal과 Prim의 결과와 동일한 것을 볼 수 있습니다.
보셨다시피 Sollin 알고리즘은 이러한 경우에 다른 알고리즘보다 빠른 속도로 동작하게 됩니다. 물론 최악의 경우에는 동일하게 비슷한 연산량으로 진행될 것입니다.
Sollin 알고리즘의 수행 시간
여기서는 n개의 정점이 있다고 할 때, 정점이 처음에는 n/2개, 그 다음에는 n/4개로 진행될 것이므로 최대 O(log n)임을 쉽게 알 수 있습니다.
각 트리에서 자신과 가까운 간선을 찾기 위해서는 최악에 모든 간선을 찾아야하므로 O(m) 시간이 걸리게 됩니다.
결국, Sollin 알고리즘오 O(m log(n))의 시간복잡도를 갖습니다.
오늘의 Sollin 알고리즘을 끝으로 MST를 찾는 알고리즘 3개에 대해서 알아봤습니다. 감사합니다.