최소 신장 트리 (MST)
무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리
KRUSKAL 알고리즘
간선을 하나씩 선택해서 MST를 찾는 알고리즘이다.
모든 간선을 가중치에 따라 오름차순으로 정렬한다.
가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다.
단 사이클이 존재할 시 다음으로 가중치가 낮은 간선을 선택한다.
n-1개의 간선이 선택될 때까지 위의 과정을 반복한다.
PRIM 알고리즘
KRUSKAL과 달리 임의의 정점을 하나 선택해서 시작한다.
선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택한다.
모든 정점이 선택될 때 까지 위의 과정을 반복한다.
PRIM 에서는 서로소인 2개의 집합 정보를 유지한다.
1.트리 정점(MST)를 만들기 위해 선택된 정점들
2.비트리 정점들 - 선택되지 않은 정점들
