다음 문제를 살펴봅시다:
한 항공사가 $n$개의 도시 사이에서 $m$개의 항공편을 운영하고 있으며, 그중 $i$번째 항공편의 운영 비용은 $w_i$루블입니다. 또한 어느 도시에서든 다른 모든 도시로 갈 수 있습니다. 나라에 위기가 닥쳐, 남은 항공편의 운영 비용이 가장 적게 들도록 하면서 가능한 한 많은 항공편을 폐지해야 합니다.
다시 말해, 주어진 무방향 그래프의 부분 그래프이면서 가중치가 최소인 트리를 찾아야 합니다. 왜 트리입니까? 그렇지 않다면 그 안에 사이클이 존재할 것이고, 그 사이클에서 어떤 간선을 제거하여 더 최적인 답을 얻을 수 있기 때문입니다. 그리고 트리가 둘 이상이라면 어떤 두 정점은 서로 연결되지 않은 채로 남게 됩니다.
이러한 트리를 신장 트리라고 부릅니다(골격, 뼈대라고도 하며, 러시아어 원어는 첫 음절에 강세가 있지만 그렇게 발음하는 사람은 거의 없습니다. 영어로는 minimum spanning tree이며, 직역하면 최소 덮개 트리입니다).
이 글에서는 신장 트리를 찾는 알고리즘과 이에 관한 고전적인 문제들을 살펴보겠습니다.