최소 스패닝 트리

a.k.a 최소 신장 트리

사이클없이 모든 정점이 간선으로 연결된 트리로, 최소 스패닝 트리를 구성하는 비용은 그 어떠한 비용보다 작아야한다.

정점(N)과 간선(E)의 개수에 따라 시간복잡도를 최소로 하는 알고리즘을 골라 쓸 수 있다.

크루스칼 알고리즘은 O(ElogE), 프림 알고리즘은 O(N^2)로 개수에 따라 골라쓴다.

크루스칼 알고리즘 구현 시 기억할 것은 Union Find

프림 알고리즘 구현 시 기억할 것은 최소 우선순위 큐