1. 개요
솔린 알고리즘은 각 단계에서 여러 개의 간선을 선택한다. 한단계의 시작점에서 선택된 간선들은 n 개의 모든 그래프 정점들을 포함한 신장 포리스트가 된다. 각 단계에서는 포리스트에 있는 각 트리에 대해 하나의 간선을 선택한다. 이 간선은 오직 하나의 정점만 그 트리에 속한 최소 비용 간선이다.
선택된 간선은 구축중인 신장 트리에 추가된다. 포리스트에 있는 두개의 트리가 같은 간선을 선택할 수 있음에 유의해야한다. 그래서 같은 간선의 복사본들이 제거된다. 또한 비용이 같은 간선이 그래프 내에 여러개 존재할 경우, 두개의 트리가 그들을 연결하는 두 개의 상이한 간선을 선택할 수도 있다.
이 간선들은 물론 동일한 비용을 갖는다. 이 중에 하나만 선택된다. 첫 번째 단계가 시작할 때는 선택된 간선의 집합이 공백이다. 이 알고리즘은 어느 한단계의 끝에서 오직 하나의 트리만이 존재하게 되거나 더 이상 선택할 간선이 없을 때 종료된다.
2. 설명
솔린 알고리즘은 각 단계에서 여러 개의 간선을 선택한다. 한단계의 시작점에서 선택된 간선들은 n 개의 모든 그래프 정점들을 포함한 신장 포리스트가 된다. 각 단계에서는 포리스트에 있는 각 트리에 대해 하나의 간선을 선택한다. 이 간선은 오직 하나의 정점만 그 트리에 속한 최소 비용 간선이다.
선택된 간선은 구축중인 신장 트리에 추가된다. 포리스트에 있는 두개의 트리가 같은 간선을 선택할 수 있음에 유의해야한다. 그래서 같은 간선의 복사본들이 제거된다. 또한 비용이 같은 간선이 그래프 내에 여러개 존재할 경우, 두개의 트리가 그들을 연결하는 두 개의 상이한 간선을 선택할 수도 있다.
이 간선들은 물론 동일한 비용을 갖는다. 이 중에 하나만 선택된다. 첫 번째 단계가 시작할 때는 선택된 간선의 집합이 공백이다. 이 알고리즘은 어느 한단계의 끝에서 오직 하나의 트리만이 존재하게 되거나 더 이상 선택할 간선이 없을 때 종료된다.
2. 설명
'공부 > 0x11 ALGORISM' 카테고리의 다른 글
| 솔린(Sollin) 알고리즘 (0) | 2012/01/18 |
|---|---|
| 프림(Prim) 알고리즘 (0) | 2012/01/18 |
| 크루스칼(Kruskal) 알고리즘 (0) | 2012/01/18 |
