최소 신장 트리(MST)

그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법

 

크루스칼, 프림 2가지가 존재

 

크루스칼

 간선 중 최소 값을 가진 간선부터 연결

 사이클 발생 시 다른 간선 선택

 주로 간선 수가 적으면 사용

 O(ElogE)

 

 프림
  임의의 노드에서 시작

  연결된 노드의 간선 중 낮은 가중치를 갖는 간선을 선택

  간선의 개수가 많을 때 크루스칼 보다 유리하다. 

  O(ElogV)