Hoon222y

MST 는 Minimum Spanning tree 인데 용어를 간략히 정리하자면 스패닝 트리 : 그래프에서 일부 간선을 선택해 만든 트리최소 스패닝 트리: 스패닝 트리 중에 선택한 간선의 가중치의 합이 최소인 트리 (트리의 정의 : 정점이 N개라면 간선은 N-1개인 경우 ) MST를 구현하는 방법에는 크게 3가지로 나누어 볼 수 있는데1) 프림 (Prim) - 정점을 중심으로 2) 크루스칼 (Kruskal) - 간선을 중심으로 3) 솔린 알고리즘 (sollin's algorithm)으로 나누어 볼 수 있다. 근데 보통은 같은 시작 복잡도를 가지고 있으므로 간단한 크루스칼을 많이 사용하는것 같다. 해당 포스팅에서는 크루스칼까지만 언급을 하도록 하겠다. 먼저 프림(Prim algorithm)의 경우1. 그래..