이번에는 최소 스패닝 트리 (Minimum Spanning Tree 약칭 MST)에 대해 이야기 해보려고 한다. MST란? 최소 스패닝 트리로 스패닝 트리 중 간선의 가중치의 합이 최소인 트리이다. 그럼 스패닝 트리는 무엇일까? 그래프에 n개의 정점이 있을때 n-1개의 간선으로 모든 점을 이은 트리이다. 사이클이 존재하지 않으며, 임의의 두 정점에 대해서 이동할 수 있는 경로가 유일하다. 다시 말하자면 그래프에서 n-1개의 간선을 뽑아내 사이클이 없는 트리를 완성하고 이때의 간선의 가중치의 합이 최소이면 이를 최소 스패닝 트리, 즉 MST라고 한다. MST를 구하는 방법 그래프에서 MST를 구하는 방법에는 크게 두가지가 있다. 바로 크루스칼 알고리즘과 프림 알고리즘이다. 둘 다 그리디를 기반으로 하고 있..
