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

신장 트리(Spanning Tree)

그래프의 모든 노드(node)를 연결하면서 사이클이 없는 부분 그래프.

노드가 n개 이면, 신장 트리의 간선(edge)의 수는 n - 1개이다.

Spanning Tree

 

 

최소 신장 트리(Minimum Spanning Tree)

 각 간선(edge)이 가지고 있는 가중치의 합이 최소가 되는 신장 트리.

대표적인 알고리즘으로는 프림 알고리즘(Prim's Algorithm)과 크루스칼 알고리즘(Kruskal's Algorithm)이 있다.