Minimum spanning tree를 구하는 알고리즘

위 그림  출처 :http://findfun.tistory.com/385

정의

최소비용 신장트리란 spanning tree의 모든 간선의 가중치 합이 최소인 그래프를 가리켜 '최소 비용 신장 트리'라고 한다.
최소비용 신장트리에는 사이클이 생겨서는 안된다.(트리의 기본조건)

구현 알고리즘

1) 크루스칼 

가중치를 기준으로 간선을 정렬한 후에 MST가 될 때까지 간선을 하나씩 선택 또는 삭제해 나가는 방식

시간복잡도

크러스컬 알고리즘은 O(Elog V) 시간 안에 동작한다고 증명

2)프림

하나의 정점을 시작으로 MST가 될 때까지 트리를 확장해 나가는 방식

시간복잡도

참고:

https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98