[MST 개념] 최소 비용 신장 트리

최소 비용 신장 트리 [ Munimum Spanning Tree ] 신장 트리(Spanning Tree) Spanning Tree : 그래프 내의 모든 정점이 간선으로 연결되어 있고, 간선들 사이에 사이클이 없는 그래프. Spanning Tree = 신장 트리 = 스패닝 트리 신장트리를 구성하는 방법은 유일하지 않다. N개의 정점을 가지는 그래프의 최소 간선의 수는 (N - 1)개 이고, 모든 정점이 (N - 1)개의 간선으로 연결되어 있으면 필연적으로 트리의 형태로 이루어질 수 밖에 없다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다. 최소 비용 신장 트리(Minimum Spanning Tree) MST(Minimum Spanning Tree)..