[알고리즘] MST, 최소 스패닝 트리(특징, 구현방법, 시간복잡도)

특징

모든 정점을 연결하는 최소 경로를 찾는 알고리즘

모든 정점 n개를 연결하므로 간선은 n-1개를 가진다

음수 간선을 가질 경우, 성립할 수 없다.( 벨만-포드 알고리즘 사용)

 

구현방법

크루스칼, 프림 알고리즘

 

시간복잡도

크루스칼로 구현할 경우 Union-Find는 상수 시간 복잡도를 가지므로 정렬하는 알고리즘에 의해 좌우된다.