최소 신장 트리 MST, Minimum Spanning Tree가중치가 있는 연결 그래프에서 모든 정점을 연결하는 간선들의 부분 집합 중에간선들의 가중치 합이 최소가 되는 트리즉, 스패닝 트리 중 간선의 가중치 합이 최소인 트리스패닝 트리 Spanning Tree 그래프 내의 모든 정점을 포함하는, 그래프의 최소 연결 부분 그래프 n 개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1) 이고, (n-1) 개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 된다 -> 스패닝 트리!MST 특징1. n 개의 정점을 가지는 그래프에서 최소 신장 트리는 n-1 개의 간선을 가진다(단, 모든 정점이 반드시 연결된 경우에만 성립하며, 가중치가 음수인 경우는 해당되지 않는다)2. 사이클이 없고 모든 정점이 연결되..
