<aside>
💡 **그래프에서 최소 비용 문제
- 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 ⇒ 최소 신장 트리
- 두 정점 사이의 최소 비용의 경로 찾기 ⇒ 최단 경로**
</aside>
mst,prim, dikstra모두 greedy한 접근법이다.
신장트리란?
- n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리
n개의 정점에서 n-1개의 간선을 사용하면, 최소한 하나의 정점이 떨어지는 경우는 없다.
신장 트리란 정점들을 고립되지 않은 무향(양방향) 그래프
최소 신장트리
- 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장트리
최소 신장 트리 알고리즘