최소 신장 트리(MST, Minimum Spanning Tree)란? - 가중치가 있는 무향 그래프가 주어졌을 때 모든 노드를 연결하면서 간선의 가중치 합이 최소인 신장 트리를 뜻한다. 최소 신장 트리의 특징 1) 가중치의 합이 최소 2) N개의 노드에 대하여 N-1개의 간선으로 구성 3) 사이클이 존재하지 않아야 함 최소 신장 트리를 구하는 방법 그래프가 주어졌을 때 우리는 어떻게 최소 신장 트리를 찾을 수 있을까? 간단한 방법으로 가중치가 작은 간선을 선택할 수 있는지 확인하여 포함하는 Greedy 방식으로 MST를 구할 수 있다. * 가중치가 작은 순서대로 간선을 탐색하면서 Spanning Tree의 조건에 부합하는 간선만 선택 * 간선을 선택시에 사이클이 있는지 여부를 판단해서 해당 간선을 연결할..