Minimum Spanning Tree(MST) 문제는 그래프에서 모든 정점을 연결해주는 최소 간선의 집합 중 가중치의 합이 가장 작은 간선의 집합을 찾는 문제입니다. MST를 구하는 방법은 크게 2가지가 있습니다. Prim algorithm과 Kruskal algorithm이죠. Prim과 Kruskal의 기본적인 아이디어는 다음과 같습니다. Prim algorithm은 각 정점을 방문하며 그 정점에 연결된 가장 가중치가 작은 간선들을 선택하여 MST를 구합니다. Kruskal algorithm은 각 간선들을 탐색하여 가장 가중치가 작은 간선들을 택하면서 MST를 구합니다. 지금부터, 아래와 같은 그래프를 가지고 Prim algorithm과 Kruskal algorithm의 동작과정을 알아보고 각 알고..