MST

Spanning Tree

• 개념: 모든 노드가 연결되어 있으며 트리의 속성을 만족하는 그래프
• 특징
  • 본래의 그래프의 모든 노드를 포함해야 함
  • 모든 노드가 서로 연결
  • 트리의 속성을 만족시킴 (사이클이 존재하지 않음)

---

Minimum Spanning Tree(MST)

최소 신장 트리

• 개념: Spanning Tree 중 간선의 가중치 합이 최소인 것

• 알고리즘 종류

  • Kruskal’s algorithm
  • Prim's algorithm