최소 신장 트리 MST (Minimum Spanning Tree)
개요
- 신장 트리 : 그래프의 모 든 정점을 포함하는 트리
- 최소 신장 트리 : 신장 트리들 중 가장 간선들 가중치의 합이 최소인 신장 트리
관련 알고리즘
Kruskal
- 각 간선의 가중치가 낮은 순으로 정렬
- 가장 가중치가 낮은 간선 순으로 탐색
- 해당 간선을 트리에 포함할 때 사이클이 없는 경우 -> 포함
- 해당 간선을 트리에 포함할 때 사이클이 있는 경우 -> 제외
Prim
- 시작 정점에서 이동 가능한 간선 탐색
- 가장 가중치가 낮은 간선 순으로 탐색
- 해당 간선을 트리에 포함할 때 사이클이 없는 경우 -> 포함
- 해당 간선을 트리에 포함할 때 사이클이 있는 경우 -> 제외
Disjoint-set, Union find
사이클이 존재하는 지 여부를 판별하기 위해 Disjoint-set 및 Union Find 알고리즘을 활용
Disjoint-set
서로소 집합
- 서로 같은 원소를 가지지 않는 두개 이상의 집합
- 트리의 사이클 존재 여부 판별에 활용
Union Find
합집합 찾기
- Disjoint-set 에서 합집합을 찾는 알고리즘
- 두 개의 정점이 동일한 집합에 속하는 지 판단할 때 활용