MST

Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리

Spanning Tree\
Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리

Prim

과정
임의의 정점을 선택하여 비어있는 T에 포함시킨다. (이제 T는 노드가 한 개인 트리. )
1. T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.
2. 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다. 
(step 1에서 찾은 간선도 같이 T에 포함됩니다.)
3.  모든 노드가 T 에 포함될 때 까지, 1,2 를 반복한다.

시간 복잡도 : O(E log V), E = 간선의 개수, V = 정점의 개수

Kruskal

그래프 간선들을 가중치의 오름차순으로 정렬해 놓은 뒤, 사이클을 형성하지 않는 선에서 정렬된 순서대로 간선을 선택합니다.

시간복잡도 : O(E log E)