솔린 알고리즘이란?(What is a Sollin Algorithm)
솔린 알고리즘은 최소 비용 신장 트리를 구하는 알고리즘중 하나로 크루스칼 알고리즘과 프림 알고리즘처럼 간선을 하나씩 선택하는 것이 아닌 동시에 여러 개의 간선을 선택하여 트리를 만드는 알고리즘이다. 솔린 알고리즘을 설명하기 전 포레스트(Forest)라는 용어의 정의가 필요하다. 포레스트란 서로 연결되지 않은 트리들의 집합 또는 연결되지 않은 비순환 그래프의 집합을 말한다. 그림으로 표시하면 다음과 같다.
그림을 보면 두 그래프는 서로 순환하지 않은 그래프이면서 서로 연결되어 있지 않다. 이런 자료 구조를 포레스트라고 한다.(정점만 있는 그래프나 하나의 트리도 포레스트가 될 수 있다.) 이제 솔린 알고리즘을 설명할 수 있다. 솔린 알고리즘은 초기에 n개의 포레스트부터 시작한다. n개의 포레스트란 결국 정점이 n개라는 의미이다. 여기서 각 정점에 인접한 간선에서 가장 비용이 적은 간선을 선택한다. 그러면 간선이 겹치는 경우가 생긴다. 이런 경우는 중복된 간선중 하나는 없애준다. 그러면 특별한 경우가 아니면 2개이상의 트리가 나온다. 여기서 각 트리의 인접한 간선중에 트리를 이어줄 수 있는 간선중 최소 비용 간선을 택한다. 이때 싸이클을 만들지 않도록 조심해야 한다. 이런 방식으로 간선의 개수가 n-1이 되면 최소 비용 신장 트리가 완성된 것이다. 다음은 솔린 알고리즘을 수행하는 과정이다.
그래프와 가중치 표
다음은 솔린 알고리즘을 적용할 그래프와 그래프의 간선들의 가중치를 나타낸 표이다.
1단계
모든 정점에서 인접한 간선중 가장 작은 비용을 가지는 간선을 선택한다. 이때 중복이 되는 경우는 중복되지 않도록 하나는 지워준다.
2단계
각 트리에서 가장 작은 간선을 선택한다. 이 경우에는 (2, 6)을 선택하면서 신장 트리가 완성된다.
솔린 알고리즘 종료
솔린 알고리즘은 상황이 좋으면 한번에 최소 비용 신장 트리를 만들 수 있다. 다음은 솔린 알고리즘을 gif로 나타낸 것이다.
'알고리즘' 카테고리의 다른 글
| 순차검색(sequential search) (0) | 2022.06.23 |
|---|---|
| 들어가기 앞서 (0) | 2022.06.23 |
| 다익스트라 알고리즘(Dijkstra Algorithm) (0) | 2022.03.31 |
| 프림 알고리즘(Prim Algorithm) (0) | 2022.03.31 |
| 크루스칼 알고리즘(Kruskal Algorithm) (0) | 2022.03.30 |