Sollin algorithm

1. 개요
솔린 알고리즘은 각 단계에서 여러 개의 간선을 선택한다. 한단계의 시작점에서 선택된 간선들은 n 개의 모든 그래프 정점들을 포함한 신장 포리스트가 된다. 각 단계에서는 포리스트에 있는 각 트리에 대해 하나의 간선을 선택한다. 이 간선은 오직 하나의 정점만 그 트리에 속한 최소 비용 간선이다.

선택된 간선은 구축중인 신장 트리에 추가된다. 포리스트에 있는 두개의 트리가 같은 간선을 선택할 수 있음에 유의해야한다. 그래서 같은 간선의 복사본들이 제거된다. 또한 비용이 같은 간선이 그래프 내에 여러개 존재할 경우, 두개의 트리가 그들을 연결하는 두 개의 상이한 간선을 선택할 수도 있다.

이 간선들은 물론 동일한 비용을 갖는다. 이 중에 하나만 선택된다. 첫 번째 단계가 시작할 때는 선택된 간선의 집합이 공백이다. 이 알고리즘은 어느 한단계의 끝에서 오직 하나의 트리만이 존재하게 되거나 더 이상 선택할 간선이 없을 때 종료된다. 

2. 설명

 

출처 : http://blog.nextcube.pe.kr/195