그래프

08-7 최소 신장 트리

최소 신장 트리(minimum spanning tree)란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.

최소 신장 트리의 특징

• 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
• N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개다.

최소 신장 트리는 에지리스트(인접리스트 아님)으로 초기화하고, 유니온 파인드를 반복해주면 된다.