[ Algorithm ] Sollin's Algorithm 이란?

Sollin's Algorithm 이란?

        최소 비용 신장 트리를 구하는 알고리즘 중 하나로, Prim's Algorithm과 달리  간선(Edge)를 하나씩 선택하는 것이 아닌

        동시에 여러 개의 간선(Edge)을 선택하여, Tree를 만드는 알고리즘이다.

 

        Sollin's Algorithm을 알기 전, Forest를 

Sollin's Algorithm 동작

        1. 각각의 단계마다, 신장 트리 집합 내 Vertex를 포함한 몇 개의 Edge를 선택합니다.

            (Prim's Algorithm, Kruskal's Alogrithm과 다르게, 2개 이상 Edge를 선택하는 것이 가능합니다.)

        

        2.  각 트리는 다른 트리와 연결할 수 있는 최소 비용의 Edge를 선택합니다.

             (중복되는 Edge는 제거합니다.)

         

        * 만약, 비용이 동일하고, 그래프의 가운데 Vertex가 있는 경우, Cycle 형성이 가능합니다.

 

        3. 만약, 선택 가능한 Edge가 없거나, 하나의 tree가 형성된다면, 종료합니다.

Sollin's Algorithm의 구체적인 원리

1단계

   모든 Vertex에서 인접한 Edge중 가장 작은 비용을 가지는 Edge을 선택한다. 이때, 중복이 되는 경우

   중복되지 않도록 지워줍니다 !

2단계

   각 트리에서 가장 작은 비용의 Edge를 선택합니다.

종료

Author's GitHub

https://github.com/kalelpark