32. 최소비용 신장 트리

최소비용 신장 트리란?

가중치 그래프에서 모든 정점을 포함하면서 간선의 가중치 합이 최소인 트리를 의미한다.

즉, 그래프에서 일부 간선을 선택하여 트리를 만들었을 때, 선택한 간선의 가중치 합이 최소인 트리를 구하는 것이다.

 

최소비용 신장 트리를 사용하는 이유?

네트워크 설계, 회로 기판 설계, 도로 건설 등 다양한 분야에서 활용된다.

 

최소비용 신장 트리를 찾는 알고리즘은?

Kruskal, Prim, Sollin 알고리즘이 있으며 앞으로 이 3가지 알고리즘에 대해서 알아보고자 한다.