최소 스패닝 트리 (1) 썸네일형 리스트형 MST 최소 신장 트리 Sollin, Boruvka (솔린, 보르부카) 알고리즘 구현 이 게시글에서는 솔린, 해외에서는 보르부카라는 이름으로 더 알려져 있는 MST 생성 알고리즘을 구현해보겠다. 솔린 알고리즘의 간단한 설명 주어진 그래프에서 각 노드들을 트리라 생각한다. 그러면 그래프는 포레스트가 된다. 각 트리에서 다른 트리로 연결된 최소 비용 엣지를 택하여 그 엣지로 연결된 두 트리를 union하는 것을 포레스트가 하나의 트리가 될 때까지 반복하면 MST가 완성된다. 단계마다 모든 엣지들을 탐색하면서 포레스트에 들어있는 트리의 개수가 절반씩 줄어들다가(한 트리는 다른 트리와 무조건 짝지어지게 됨을 생각하면 이해할 수 있다.) 1개, 즉 MST가 되면 종료하므로 시간 복잡도는 $O(ElogV)$이다. 구현 - 백준 1197번 풀기 union하는 것에서 눈치챌 수 있듯이 솔린 알고리즘도 .. 이전 1 다음
