최소 신장 트리

최소 신장 트리 minimum spanning tree

 

모든 노드를 연결할 때 사용된 에지의 가중치의 합을 최소로 하는 트리

사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음

n개의 노드가 있으면 최소 신장 트리 구성 에지 개수는 n-1이다.

---

1. 에지 리스트로 그래프 구현, 유니온 파인드 리스트 초기화

2. 그래프 데이터를 가중치 기준 정렬

3. 가중치가 낮은 에지부터 연결 시도

사이클 형성 여부 find로 확인 후

사이클이 아닌 경우에만 union 연산으로 두 노드 연결

 

4. 연결 에지 개수 n-1만큼 반복

 

5. 에지 개수 n-1인 경우 종료

완성된 최소 신장 트리의 총 에지 비용 출력