[알고리즘] 최소 신장 트리 (MST, Minimum Spanning Tree)

개념 Spanning Tree 란 - 그래프 내의 모든 정점을 포함하는 트리 - Spanning Tree = 신장 트리 = 스패닝 트리 - Spanning Tree는 그래프의 최소 연결 부분 그래프 이다. (최소 연결 = 간선의 수가 가장 적다, n개의 정점을 가지는 그래프의 최소 간선 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다.) - 즉, 그래프에서 일부 간선을 선택해서 만든 트리 MST 란 - Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 - MST = Minimum Spanning Tree = 최소 신장 트리 - 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선..........