참고
신장트리(Spanning Tree)
NOTE
Spanning Tree ⇒ 가능한 최소 개수의 간선으로 모든 정점을 포함하는 그래프 G의 하위집합!
1개의 완전 그래프에서 3개의 신장트리를 발견했다!
•
완전한 무방향 그래프는 최대 n^n-2개의 신장트리를 가질 수 있다.
•
n개의 정점을 가지는 그래프가 n-1개의 간선을 가진다면 필연적으로 신장트리가 된다.
신장트리 특징
NOTE
•
DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다
•
하나의 그래프에는 많은 신장 트리가 존재할 수 있다
•
모든 정점들이 연결되고, 사이클을 포함해서는 안된다.
최소비용 신장트리 (MST - Minimum Spanning Tree)
NOTE
최소비용 신장트리 ⇒ 트리를 구성하는 간선들의 가중치를 합한것이 최소가 되는 신장 트리!
신장트리는 여러개가 나올 수 있지만, 그중 가중치가 가장 적은걸 선택
•
대표적인 알고리즘으로 크루스칼 알고리즘, 프림 알고리즘이 존재한다.