[Algo] Minimum Spanning Tree (MST)

Spanning Tree

input: 아무 그래프
output: 그래프 내의 모든 정점을 포함하는 트리

* 트리이므로 사이클이 있어서는 안된다.

 

Minimum Spanning Tree

input: 방향없는 weighted edge 그래프
output: cycle 없는 edge cost가 최소인 spanning tree
(같은 cost인 그래프가 여러개 나올 수도 있다.)

 

 

 

 

Kruskal's Algorithm

input: 방향없는 weighted edge 그래프
output: cycle 없는 edge cost가 최소인 spanning tree

0) weight순으로 edge를 sorting한다

1) weight이 가장 작은 edge를 선택한다, cycle을 만들지 않는다면 추가

 

시간복잡도

O(NlogN) : sorting하느라 사용되는 시간

 

Prim's Algorithm

[Kruskal과 다른점]
처음 노드를 하나 뽑는다. 기존에 봤던 노드 근처에 있는 애들에서만 뽑을 수 있다.

0) 노드를 하나 뽑는다

1) 그 노드에 이어진 weight이 가장 작은 edge를 선택한다, cycle을 만들지 않는다면 추가