신장트리, 최소신장트리

1. 신장트리(Spanning Tree)

원래 그래프의 모든 노드가 연결되어 있으면서, 사이클이 존재하지 않는 그래프

 

2. 최소 신장트리(Minimum Spanning Tree)

신장트리 중 간선의 가중치 합이 최소인 신장트리