스패닝 트리는 무방향 그래프에서

1. 모든 정점들이 연결됨
2. 사이클이 없음.

즉, 한 그래프에서 여러 스패닝 트리가 나올 수 있음.

최소 스패닝 트리는 이러한 스패닝 트리 중 가중치의 합이 가장 작은 트리이다.

1. 크루스칼의 최소 스패닝 트리 알고리즘
2. 프림의 최소 스패닝 트리 알고리즘

둘 다 간선이 하나도 없는 상태에서 시작해 하나씩 트리에 간선을 추가해 가는 탐욕적 알고리즘.

크루스칼

프림