자료구조: 최소 신장 트리(MST, Minimum Spanning Tree, 최소 스패닝 트리)

Spanning Tree (신장 트리)

Spanning Tree란 그래프 내의 모든 정점을 포함하는 최소 연결 부분 그래프를 뜻한다. (신장 트리라고도 한다)
n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, 

모든 정점이 (n-1)개의 간선으로 연결되어 있으면 Spanning Tree가 된다.

특징

1. DFS, BFS등 탐색 기법을 사용하면 그래프에서 특정 신장 트리를 찾을 수 있다.
2. 하나의 그래프에는 여러 신장 트리가 존재할 수 있다.

3. 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다.
4. Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다.

---

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

MST란 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리를 뜻한다.

 

MST의 특징

1. 정점 간 간선의 가중치의 합이 최소여야 한다.
2. n개의 정점을 가지는 그래프에 대해 (n-1)개의 간선을 사용해야 한다.
3. 사이클이 포함되어서는 안된다.

MST의 사용 사례

도로 건설
  도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제
전기 회로
  단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제
통신
  전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제
배관
  파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 연결하는 문제

 

 

 

참고: https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html