스패닝 트리(Spanning Tree)는 무방향 그래프의 부분 집합으로, 그래프의 모든 정점을 최소한의 간선으로 연결한 트리를 의미합니다.
그래프의 모든 정점이 서로 연결되어 있다면 반드시 하나 이상의 스패닝 트리가 존재합니다. 또한 하나의 그래프에는 두 개 이상의 스패닝 트리가 동시에 존재할 수도 있습니다.
최소 스패닝 트리란?
최소 스패닝 트리(Minimum Spanning Tree, MST)는 연결된 가중치 무방향 그래프에서 모든 정점을 연결하면서 간선 가중치의 총합이 최소가 되는 간선들의 부분 집합입니다. MST를 구하는 대표적인 방법으로는 프림(Prim) 알고리즘과 크루스칼(Kruskal) 알고리즘이 있으며, 이 장에서는 프림 알고리즘을 중심으로 살펴보겠습니다.
앞서 언급했듯이 하나의 그래프에는 여러 개의 스패닝 트리가 존재할 수 있습니다. 정점의 개수가 n개라면 스패닝 트리는 반드시 n - 1개의 간선을 가져야 한다는 점이 중요합니다. 만약 그래프의 각 간선에 가중치가 부여되어 있고 스패닝 트리가 여러 개 존재한다면, 그중에서 가중치의 합이 가장 작은 최소 스패닝 트리를 찾아야 합니다.
추가로, 동일한 가중치를 가진 간선이 여러 개 존재하는 경우에는 그래프가 둘 이상의 최소 스패닝 트리를 가질 수 있습니다.
위 그래프는 스패닝 트리의 한 예시를 보여주지만, 최소 스패닝 트리는 아닙니다. 이 스패닝 트리의 비용은 (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38입니다.