최소신장트리

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

 

신장트리(Spanning Tree)란 그래프의 모든 노드를 포함하고, 모든 노드가 서로 연결되어 있고, 트리의 속성을 만족하는 그래프를 뜻합니다.

최소신장트리(MST)란 신장트리 가운데 노드 가중치의 합이 최소인 신장트리를 뜻합니다.

노드 사이를 잇는 거리/비용 등을 최소로 하는 그래프를 의미합니다.

MST 를 찾아내는 기법에는 크루스칼 알고리즘, 프림 알고리즘이 있습니다.