S E P H ' S

MST(Minimum Spanning Tree) 최소 신장 트리 그래프의 모든 정점을 사이클 없이 잇는 (신장 트리) 트리에서 간선의 가중치의 합이 최소가 되는 트리를 말한다. 크루스칼 알고리즘 간선 중심으로 최소 신장 트리를 구하는 알고리즘. 간선이 적을때 프림 알고리즘보다 유리하다. 내부적으로 union-find 알고리즘을 사용 간선들을 가중치의 오름차순 정렬하여 가장 작은 간선을 선택한다. 그 간선이 지금까지 만들어진 MST와 싸이클을 형성한다면 제외하고 아니라면 MST에 추가한다. 모든 간선에 대해 반복한다. 프림 알고리즘 정점 중심으로 최소 신장 트리를 구하는 알고리즘 정점이 적을때 크루스칼 알고리즘보다 유리 임의의 정점 선택 그 정점과 인접한 정점을 잇는 간선 중 가중치가 가장 낮은 간선 선택..