Motivation

크루스칼(Kruskal) 알고리즘은 선택된 간선들로 이루어진 성장하는 포레스트(forest)를 union-find 구조로 유지합니다. 간선을 안전하게 추가하기 위해, 두 끝점이 이미 같은 집합에 있는지 확인합니다(같은 집합에 있다면 사이클이 형성됩니다).

왜 크루스칼을 배워야 할까요?

• 실제 MST 활용 사례: 네트워크 설계, 클러스터링, 최소 비용으로 케이블이나 도로 부설.
• Union-find: 컴퓨터 과학 전반에서 나타나는 연결성 추적을 위한 아름답고 재사용 가능한 구조입니다.
• 탐욕적 선택의 정당성(Greedy correctness): 항상 가장 저렴하고 안전한 옵션을 선택하는 것이 전역 최적해(global optimum)를 도출하는 또 다른 예시입니다.

그래프의 모든 최소 신장 트리(MST)는 동일한 간선 가중치의 다중 집합(multiset)을 사용하므로, 전체 가중치(및 가장 큰 간선)는 유일합니다.