[Algorithm] 최소 신장 트리(Minimum Spanning Tree)

최소 신장 트리(MST)

• 그래프에서 모든 노드를 연결할 때 사용된 간선의 비용을 최소로 하는 트리로 다음과 같은 특징을 가지고 있습니다.

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

최소 신장 트리의 단계

1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화

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

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

• 가중치가 낮은 에지부터 시작 노드와 도착 노드를 find 연산을 통해 연결합니다.
• 이때 시작 노드와 도착 노드의 부모 노드가 같다면 연결 시 사이클이 발생하므로 연결하면 안됩니다.

4. N-1번 반복 후 총 간선 비용 구하기