최소 스패닝 트리란? 최소 스패닝 트리(Minimum spanning tree) 는 그래프 이론에서 자주 사용하는 개념이다. 최소 신장트리, MST라고도 부르는데 다 같은 말이다. 스패닝 트리 / 최소 스패닝 트리 '최소 스패닝 트리'를 살펴보기에 앞서, 먼저 '스패닝 트리'를 이해해보자. 스패닝 트리는 어떤 그래프에서 모든 정점을 포함하지만, 사이클이 발생하지 않는 트리다. 다음 그래프를 보면서 이해해보자. 위 그래프는 사이클이 있다. 1번, 2번, 3번 노드가 서로 사이클을 발생시킨다. 사이클을 없애면서 모든 노드를 포함하는 그래프는 다음과 같은 모양이 될 것이다. 위에 보이는 그래프들 모두 '스패닝 트리' 다. 사이클이 없고 모든 노드를 포함하기 때문이다. 이때 스패닝 트리의 '가중치'를 물어본다면..
