💡 크루스칼 알고리즘?
탐욕적인 방법을 이용하여 네트워크의 모든 정점을 최소 비용으로 연결하는 최적의 해답을 구하는 것
➡ 사이클을 형성하지 않는 한붓 그리기
간선 위주의 알고리즘. 시작점을 따로 정하지 않고 최소 비용의 간선을 차례로 대입하면서 트리를 구성하기 때문에 사이클이 이루어지는지 항상 확인.
탐욕적인 방법
- 결정을 해야할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는것
- 크루스칼 알고리즘은 최적의 해답을 준다.
💡 크루스칼 알고리즘의 동작
- 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
- 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
-> Union-Find이용. Find로 루트 같은 지 확인 - 해당 간선을 현재의 MST의 집합에 추가한다.
-> 같지 않다면 Union으로 집합 합쳐줌.
