크루스칼 알고리즘
- 최소 신장 트리를 찾는 알고리즘
최소 신장 트리 - 간선의 비용이 존재할때 최소 간선 비용을 들여서 만들수 있는 신장트리
오른쪽이 최소신장 트리
동작 순서
1. 주어진 모든 간선 정보에 대해 간선 비용이 낮은 순서(오름차순)로 정렬
2. 정렬된 간선 정보를 하나씩 확인하며 현재의 간선이 노드들 간의 사이클을 발생시키는지 확인
3. 사이클이 없는 경우 최소 신장 트리에 포함, 사이클이 있는경우 포함 X
4. 1~3번의 과정을 반복
간선의 정보를 가져오고
두 간선의 양 정점을 두 정점 중 작은 값으로 변경함 (Union)
최소 비용을 오름차순으로 뽑아서 반복하는 것이기때문에 제일 처음 출력되는 값이 최소 값
크루스칼 알고리즘을 사용하는 문제
--> 백준 최소 스패닝 트리
https://shin8037.tistory.com/