_

1. 소개

어떤 그래프의 스패닝 트리(Spanning Tree)는 원래 그래프의 정점 전부와 간선 일부로 구성된 트리 형태의 부분 그래프를 말합니다. 최소 스패닝 트리(MST, Minimum Spanning Tree)란 어떠한 가중치 그래프의 스패닝 트리 중 간선의 가중치 합이 가장 작은 것을 말합니다.

2. 관련 알고리즘

• Kruskal's Algorithm
• Prim's Algorithm