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

신장트리(Spanning Tree)

그래프 내의 모든 정점을 포함하는 트리
그래프에 사이클이 형성이 되면 안됨

- 그래프의 최소 연결부분 그래프
- 최소연결 = 간선 수가 제일 적다
- n개의 정점을 가지는 그래프에서 n-1 개의 간선으로 연결되어 있는 형태
- 일부 간선을 선택해서 만든 트리

 

최소 신장트리(Minimum Spanning Tree)

신장트리 중에서 사용된 간선들의 가중치 합이 최소인 트리

- 각 간선의 가중치가 동일하지 않을 때 가장 적은 간선을 사용한다고 해서 최소비용이 얻어지지 않음
- MST는 간선에 가중치를 고려하여 최소 비용의 신장트리를 선택하는 것을 의미
- 간선의 가중치의 합이 최소(n개의 정점엔 n-1개의 간선)
- 사이클이 형성 되면 안됨