크루스칼 알고리즘이란
1.
모든 정점을 독립적인 집합으로 만듦
2.
모든 간선을 비용 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교
3.
두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결
4.
최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것이 중요 (사이클 형성 시 선택하지 않음)
5.
탐욕 알고리즘을 기초로 하고 있음
(당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음)
•
사이클이 생성되는지 확인 절차가 필요함
•
이를 해결하고자 Union-Find 알고리즘을 사용
Union-Find 알고리즘에 대한 설명은 밑에 클릭