[자료구조] 신장트리(Spanning Tree) & 최소 신장 트리(MST)

1. 신장 트리(Spanning Tree)란...?

• Original 그래프에서 다음의 조건들을 만족시키는 그래프 -> (모든 노드가 연결 / 트리의 속성 만족(사이클 X))
• 신장 트리 조건
  
  1. 사이클 X
  2. Original 그래프의 모든 노드 포함
  3. 모든 노드 연결

1번째가 Original 그래프 / 2,3,4번째는 신장 트리

 

2. 최소 신장 트리(MST)란...?

• Minimum Spanning Tree
• 신장 트리 중에서, 간선의 가중치 합이 최소인 것
• 토목, 통신 등등 다양한 분야에서 활용 가능