Sollin's algorithm(Borůvka's algorithm)

최소 비용 신장 트리 구하는 알고리즘 중 가장 자료가 없는 Sollin's algorithm 혹은 (Borůvka's algorithm)에 대해서 정리를 해보겠다.

최소 비용 신장 트리는 신장트리를 만드는데, 간선의 가중치 합이 최소가 되도록하는 알고리즘이다.

 

다음과 같은 그래프가 있다고 하자.

 

각각의 정점에 연결된 간선 중 가중치가 가장 작은 간선만을 선택한다.

0->6, 1->7, 2->7, 3->12, 4->12, 5->6, 6-> 10

이제 각각의 트리들이 만들어졌는데, 가장 작은 가중치를 갖는 간선을 이용하여 이어준다.

(이것에 대한 구체적인 알고리즘은 없는 것으로 보인다.)

다음 경로가 바로 Sollin's algorithm의 결과물, 최소 비용 신장 트리이다.