최소 스패닝(신장) 트리 (Minimum Spanning Tree)

Spanning Tree

그래프 내의 모든 정점을 포함하는 트리

💡 최소 신장 트리는 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

특징

1. 사이클이 만들어지지 않아야 한다.
   1. 사이클이 만들어진 경우는 불필요한 연결이 존재한다는 뜻이기 때문
2. 전체 노드(n) -1 개의 간선으로 구성된다.
3. 하나의 그래프에 여러 개의 최소 신장 트리가 존재할 수 있다.

최소 신장 트리의 대표적인 알고리즘으로는 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 존재한다.

크루스칼 알고리즘 (Kruskal Algorithm)

동작 원리

1. 선택하지 않은 간선들 중 최소 가중치인 간선을 선택
2. 사이클이 없는 경우에만 트리에 추가
3. 총 v-1 (정점 개수 -1)개의 간선이 선택될 때까지 반복

구성한 스패닝 트리에 사이클 발생 여부를 판단하기 위해, 분리 집합 (Disjoint Set)을 사용한다.

→ Union-Find 알고리즘 사용

→ 어떤 간선을 선택했을 때, 그 간선의 두 정점이 같은 최상위 부모를 가지면 사이클이 발생함을 알 수 있다.