Boruvka 알고리즘
Boruvka 알고리즘은 그래프에서 MST를 구하는 알고리즘으로 가장 오래된 알고리즘 입니다.
처음에는 모든 노드가 각자 노드만 존재하는 트리에서 시작합니다.
각 트리에서 다른 트리로 이어지는 엣지중 가장 가중치가 작은 엣지를 찾아내고 두 트리를 연결합니다.
연결에 사용된 엣지는 MST의 엣지가 됩니다.
모든 트리가 연결되어 하나가 될 때까지 반복합니다.
구현
'알고리즘 > 그래프' 카테고리의 다른 글
| [그래프 알고리즘]kosaraju 알고리즘(SCC) (0) | 2022.07.11 |
|---|---|
| [그래프 알고리즘]Tarjan 알고리즘(SCC) (0) | 2022.07.11 |
| [그래프 알고리즘]kruskal 알고리즘(MST) (0) | 2022.07.11 |
| [그래프 알고리즘]프림 알고리즘(MST) (0) | 2022.07.11 |
| [그래프 알고리즘]존슨 알고리즘(플로이드워셜보다 좋은 이유) (0) | 2022.07.11 |