최소 스패닝 트리(MST)를 구하는 알고리즘(Kruskal, Prim)에 대해 설명해주세요.

최소 스패닝 트리(MST)를 구하는 대표적인 알고리즘으로 Kruskal과 Prim 알고리즘이 있습니다. 둘 다 탐욕 알고리즘에 기반합니다.

Kruskal 알고리즘은 가장 가중치가 작은 간선부터 시작하여 트리를 확장해 나갑니다. 핵심은 사이클을 만들지 않도록 간선을 선택하는 것입니다. 이를 위해 Union-Find 자료구조를 사용하여 각 정점이 속한 집합을 관리하고, 두 정점이 같은 집합에 속해 있다면 해당 간선을 선택하지 않습니다.

Prim 알고리즘은 특정 정점에서 시작하여 트리를 확장해 나갑니다. 이미 트리에 속한 정점과 연결된 간선 중 가장 가중치가 작은 간선을 선택하여 트리를 확장합니다. Kruskal과는 달리 항상 연결된 트리를 유지한다는 특징이 있습니다.

두 알고리즘 모두 그래프의 모든 정점을 연결하면서 가중치의 합이 최소가 되는 트리를 찾는다는 공통점이 있습니다.