Borůvka's Algorithm (1) 썸네일형 리스트형 128. Borůvka's Algorithm 보르부카 알고리즘(Borůka's Algorithm) 또는 솔린 알고리즘(Sollin's Algorithm)은 무향 그래프의 최소 스패닝 트리를 구하는 세 번째 알고리즘이며 다음과 같이 작동한다. 1. 각각의 컴포넌트에 연결된 간선들 중 가중치가 가장 작은 간선을 하나씩 선택한다. 2. 간선을 차례로 최소 스패닝 트리에 추가하는데, 간선이 연결하는 두 정점이 이미 같은 컴포넌트에 존재한다면 추가하지 않는다. 3. 컴포넌트가 하나로 줄어들 때까지 1번과 2번 과정을 반복한다. 이번에도 설명이 짧게 끝났다. 다시 예시를 가지고 살펴보자.처음에는 정점들이 모두 다른 컴포넌트에 존재하므로, 각 정점과 연결된 간선들 중 가중치가 가장 작은 것 하나를 모두 고른다.$\text{A}: \text{D}.. 이전 1 다음
