최소 스패닝 트리(MST)

신장트리 중에서 사용된 간선들의 가중치 합이 최소인 트리

최소 스패닝 트리를 구현하는 두 가지 유명한 알고리즘으로는 크루스칼 알고리즘(Kruskal Algorithm)과 프림 알고리즘(Prim's Algorithm)이 있다. 크루스칼 알고리즘은 간선 위주로 탐색을 진행하고 프림 알고리즘은 정점 위주로 탐색을 진행한다.

MST = Minimun Spanning Tree = 최소 신장 트리
각 간선의 가중치가 동일하지 않을 때 , 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것은 아니다!
최소신장트리는 간선의 가중치를 고려하여 최소 비용 신장트리를 선택하는 것을 말한다

특징

1. 간선의 가중치 합이 최소여야 한다
2. n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다
3. 사이클이 포함되어서는 안된다