최소 스패닝 트리 (MST)

스패닝 트리 : 모든 정점 포함, 순환 X
최소 스패닝 트리 : 가중치의 합을 최소로 만드는 스패닝 트리

이를 위해, 크루스칼 알고리즘, 프림 알고리즘 등이 존재

크루스칼 알고리즘.

1) 간선의 가중치를 오름차순으로 정렬
2) 가중치가 가장 작은 간선을 선택.
3) 2개의 노드가 연결 되지 않았다면 서로 연결.

프림 알고리즘

1) 그래프에서 아무 정점이나 선택
2) 선택한 정점과 선택하지 않은 정점을 연결하는 간선 중 최소값 고름
3) 선택한 간선으 MST 에 추가하고, 선택하지 않은 정점을 선택.
4) 모든 정점 선택 하지 않으면 ,다시 2번 단계로.
시간 복잡도는 O(VE) 최대 O(V^3) 이다.
우선순위큐를 사용한다면 O(ElogE) 로 줄일 수 있다.