Data Structure : 최소비용신장트리 - Sollin's Algorithm (Boruvka's Algorithm)

Data Structure : 최소비용신장트리 - Sollin's Algorithm ( Boruvka's Algorithm )

Sollin의 알고리즘은 Greedy Strategy로, 각 스텝마다 가능한 최선의 선택지를 고르는 것을 반복하여 결과를 얻어낸다.

규칙

1. 시작하면서 모든 정점을 Tree로 정의한다. ( Forest 상태 )
2. 하나의 Tree에 대해 외부의 Vertex와 연결 가능한 가장 비용이 작은 edge를 선택해 추가한다.
   • edge가 중복되는 경우에는 하나만 추가한다.
3. Tree가 하나로 이어질 때 까지 2를 반복한다. ( Forest 상태 X )

Sollin 알고리즘

모든 Vertex를 one-vertex Tree로 정의
while(tree가 하나가 아니면) {
    모든 tree에 대해서 각각 Tree에서 다른 tree로 연결된 edge 중 가장 비용이 낮은 edge를 연결
    중복된다면 하나만 연결하여 저장
}

Sollin 알고리즘의 동작방식

왼쪽의 Graph가 원본 그래프이고, 그래프를 토대로 최소비용신장트리를 구하고자 한다.

시작 정점을 3으로 지정하였다. Tree에는 현재 3만 들어있는 상태

Tree에서 뻗을 수 있는 가장 cost가 낮은 edge를 연결해가며 Tree를 확장한다.

Edge (3, 6)의 경우, 둘 다 Tree에 속해있고 최소비용의 edge도 아니기에 선택될 수 없다.

알고리즘 실행 결과로 붉은 색 edge들로 구성된 Spanning Tree를 얻을 수 있다.

Sollin 알고리즘의 시간복잡도

종료될 때 까지 매번 최대 n개, n/2개, n/4… 개의 Vertex를 검사하게 되고 ( O( log n ) ), edge를 다 검사하게 되므로 ( O ( n ) )Sollin 알고리즘의 시간복잡도는 O ( n log n ) 이다.