최소 신장 트리(Minimum Spanning Tree)는 그래프에서 모든 정점을 포함하면서 사이클이 없는 연결된 부분 그래프(트리)를 말한다. 여기서 ‘최소’는 트리를 구성하는 간선들의 가중치 합이 최소라는 의미.

주요 특징

• 정점이 n개인 그래프의 MST는 항상 n-1개의 간선을 가진다.
• 모든 정점이 연결되어 있다.
• 어떤 두 정점 사이에도 단 하나의 경로만 존재한다. (사이클이 없다)
• 간선 가중치의 합이 최소다.

크루스칼 알고리즘(Kruskal’s Algorithm)

크루스칼 알고리즘은 최소 신장 트리를 찾는 대표적인 그리디 알고리즘.

크루스칼 알고리즘의 핵심은 “가장 작은 가중치의 간선부터 사이클 없이 선택”하는 그리디 전략.

이 방법을 통해 전체 그래프의 모든 정점을 최소 비용으로 연결할 수 있다.

알고리즘 단계

1. 모든 간선을 가중치에 따라 오름차순으로 정렬
2. 가중치가 가장 작은 간선부터 선택하되, 해당 간선이 사이클을 만들지 않는 경우에만 선택
3. n-1개의 간선이 선택될 때까지 2번 과정을 반복

사이클 감지 방법

사이클 감지는 유니온-파인드(Union-Find) 자료 구조를 사용한다.