크루스칼(Kruskal)의 MST 알고리즘 Kruskal 알고리즘은 탐욕적인 방법(Greedy, 그리디)를 사용합니다. 그리디를 간략하게 설명하자면, 선택할 때마다 그 순간 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방법입니다. 그리디는 근사적인 방법이기 때문에 항상 최적의 해답을 주지 않을 수도 있습니다. 하지만 Kruskal의 MST 알고리즘은 최적의 해답을 주는 것으로 증명되었기 때문에 이 방법으로 최적해(최단 경로)를 구할 수 있습니다. 알고리즘의 작동 방식은 다음과 같습니다. 그래프의 간선들을 가중치의 오름차순으로 정렬함 사이클을 형성하지 않는 간선을 찾아서 최소 신장 트리의 집합에 추가함 가장 낮은 가중치를 가진 간선을 먼저 선택함 만약 사이클을 형성하는 간선이 있다면 그..