최근 수정: 6년 전
1. 개요
Spanning Tree.
그래프에서 일부 간선들을 선택해서 만든 트리.
트리는 사이클이 없으므로 그래프에서 사이클이 없게 간선을 적절히 선택한 것이다.
특히, 스패닝 트리 중에서 최소 비용(선택한 간선들의 가중치 합이 최소)이 되는 트리를 MST라 한다.
