신장트리
그래프의 모든 정점과 간선의 부분집합으로 구성되는 트리
모든 정점들이 연결되어 있어야 함
최소신장트리 (Minimum Spanning Tree)
신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리
MST 특징
- 무방향 가중치 그래프
- 그래프의 가중치의 합이 최소여야 한다.
- N개의 정점을 가지는 그래프에 대해 반드시 (N-1)개의 간선을 사용해야 한다.
- 사이클을 포함해서는 안 된다.
사용하는 이유?
도로망, 통신망, 유통망 등등 여러 분야에서 비용을 최소로 해야 그만큼의 이익을 볼 수 있다.
대표적인 방법
- 크루스칼 알고리즘
- 프림 알고리즘
