[그래프] 최소 신장 트리(MST, Minimum Spanning Tree)

Spanning Tree

 - 그래프 내의 모든 정점을 포함하는 최소 연결 부분 그래프

 - N개의 정점을 가지는 그래프의 최소 간선의 수는 (N-1) 개이며, (N-1)개의 간선으로 연결된 그래프는 Spanning Tree

   이다.

 - 모든 정점들이 연결되어 있어야 하며, Cycle을 포함하지 않아야 한다.

 

출처 : https://www.tutorialspoint.com/data_structures_algorithms/spanning_tree.htm

 

MST(Minimum Spanning Tree, 최소 신장 트리)

 - Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리

 - 즉, MST 는 아래와 같은 특징을 가진다.

• 간선의 가중치의 합이 최소
• N 개의 정점을 가지는 그래프에 대해 반드시 (N-1) 개의 간선만을 사용
• 사이클을 포함하지 않음