[Algorithm] 최소 비용 신장 트리 (MST, Minimum SpanningTree)

신장트리(SpanningTree)

그래프 중 모든 정점이 간선으로 연결되어 있고, 간선들 사이에 사이클이 없는 그래프를 의미한다. 특징으로는 N개의 정점을 가지는 그래프의 최소 간선(edge)의 수는 (N-1)개이다. 

최소 비용 신장 트리 (MST, Minimum SpanningTree)

신장 트리는 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프이다. 한 곳으로 도달하는 경우가 두 개 이상 존재하는 경우, 즉 사이클이 존재하는 경우에는 최소한의 연결이라 말할 수 없기 때문에, 모든 위치 하나에서 다른 곳으로 이동하는 경우는 단 한 가지로 결정되도록 항상 트리의 형태를 나타낸다. 최소 비용 신장 트리는 이러한 신장 트리들 중 간선의 가중치 합이 가장 작은 트리이다. 최소 비용 신장 트리는 그리디 기법을 이용하여 최적의 해를 구할 수 있으며, 프림 알고리즘과 크루스칼 알고리즘이 대표적이다. (출처: 나무위기)

위의 내용을 요약하면, 

1. 사이클이 없는 그래프
2. 가중치를 가진 그래프
3. 최소한의 연결을 한 그래프 ( N개의 정점 → N-1개의 간선 ) 
4. 트리 구조를 가지고 있는 그래프 
5. 대표적인 알고리즘은 프림, 크루스칼 알고리즘이 있다.