1. Sollin's Algorithm이란?
Sollins' Algorithm(솔린 알고리즘)은 그래프를 공부할 때 함께 배웠던 minimum cost spanning tree(최소 스패닝 트리)를 구하는 방법 중 하나이다.
이 알고리즘에서는 cost가 작은 순으로 edge를 연결하여 component를 만들고, 그 component를 다시 작은 cost의 edge로 연결하여 최소 스패닝 트리를 만든다.
2. 예시
위 그림과 같은 그래프가 있다고 하자. 솔린 알고리즘에서는 edge가 없는 forest에서 시작한다.
여기서 각 vertex의 edge들 중 가장 cost가 작은 edge를 연결한다. 만약 이미 그 edge가 연결되어 있다면, 이는 중복되어 추가되지 않는다. 이렇게 하면 총 4개의 component가 만들어진다.
그리고 각 component를 연결하는 edge 중 가장 cost가 작은 edge들을 연결한다. 이러한 방식으로 솔린 알고리즘을 이용하여 최소 스패닝 트리를 만들 수 있다.
공부하는 대학생