1. 개념 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다. 2. 특징 사이클은 없어야 한다. 사이클이 있으면 가중치의 합이 최소가 될 수 없기 때문이다. N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개다. 에지 리스트의 형태로 구현하는 것이 간단하다. 3. 종류 1) 크루스칼 모든 에지를 가중치 기준으로 오름차순으로 정렬한 후, 가중치가 작은 간선부터 선택하면서 사이클을 형성하지 않도록 하여 최소 신장 트리를 만든다. 2) 프림 시작 노드부터 출발하여 가장 가까운 노드를 선택하며, 해당 노드와 연결된 에지 중 가장 가중치가 작은 간선을 선택하는 방식으로 최소 신장 트리를 만든다. 4. 크루스칼 1) 원리 에지 리스트를 생성한다. 에지 리..