최소 신장 트리(MST)

최소 신장 트리(Minimum Spanning Tree, MST)

• 가중치 그래프에서 가중치의 합이 최소가 되는 신장 트리를 말한다.
• 최소 신장 트리를 찾는 것은 네트워크 설계, 클러스터 분석, 지리 정보 시스템 등 다양한 분야에서 중요한 문제로 다루어진다.

 

 

 

최소 신장 트리를 찾는 데에 주로 사용하는 알고리즘

1. 크루스칼(Kruskal) 알고리즘

• 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
• 가중치가 가장 낮은 간선부터 순서대로 선택하면서 신장 트리를 구성한다.
• 선택한 간선이 사이클을 형성하는 경우, 그 간선은 제외한다.
• 이 과정을 모든 정점이 연결될 때까지 반복한다.

2. 프림(Prim) 알고리즘

• 시작 정점을 선택한다.
• 선택된 정점과 인접한 간선 중에서 가중치가 가장 낮은 간선을 선택하고, 해당 간선이 연결하는 정점을 신장 트리에 추가한다.
• 이미 신장 트리에 포함된 정점들과 인접한 간선들 중에서 가장 가중치가 낮은 간선을 선택하여 트리를 확장한다.
• 이 과정을 모든 정점이 트리에 포함될 때까지 반복한다.

 

 

 

최소 신장 트리의 성질

• 최소 신장 트리는 그래프의 정점 수가 n개일 때 정확히 n−1개의 간선을 가진다.
• 최소 신장 트리는 유일하지 않을 수 있으나, 모든 최소 신장 트리의 가중치 합은 동일하다.
• 최소 신장 트리는 사이클을 포함할 수 없으며, 두 정점을 연결하는 최소 가중치 경로를 제공한다.