신장 트리
신장트리(Spanngin Tree) 란, 무방향 그래프에서 그래프 내의 모든 정점을 포함하며, 최소한의 간선 개수만을 가지는 서브 그래프입니다.
최소한의 간선만을 사용해야 하므로 사이클이 발생하면 안되고, 놓치는 정점이 발생하면 안됩니다.
이는 이름에서도 알 수 있듯이 트리의 형태입니다. 따라서 간선의 개수는 (정점의 개수 - 1) 입니다.
정점의 개수가 N개라면 신장트리의 간선 개수는 N-1 이 됩니다.
최소 신장 트리 (MST)
하나의 그래프에서 여러개의 신장트리가 만들어 질 수 있습니다.
이 중에서 각 간선의 가중치 합이 최소가 되는 신장트리가 최소 신장 트리(MST) 입니다.
MST는 다음과 같은 특징을 가집니다.
- 사이클이 존재하지 않는다.
- n개의 정점을 가지는 그래프에서 항상 n-1 개의 간선을 가진다.
- 간선의 가중치 합이 최소가 된다.
구현
Kruskal 알고리즘
탐욕법(greedy algorithm)을 이용하여 MST를 구합니다.
간선 가중치의 합이 최소, 사이클이 발생하지 않는다는 특징을 이용하여,
사이클이 발생하지 않는 간선 중 가중치가 가장 작은 간선을 선택하며 MST를 완성합니다.
- 그래프의 간선을 가중치 오름차순으로 정렬합니다.
- 정렬된 순서대로 하나씩 해당 간선이 사이클을 발생시키는지 확인합니다.
- 사이클이 발생하지 않는다면 MST간선 집합에 해당 간선을 추가합니다.
- 2, 3번 과정을 집합의 간선 개수가 n-1 이 될 때까지 반복합니다.
Prim 알고리즘
하나의 정점에서 시작하여 인접한 정점 중 간선의 가중치가 낮은 것을 선택하며 최종 MST를 완성합니다.
- MST 정점 집합에 시작 정점 하나를 넣습니다.
- 집합에 포함된 정점들과 인접한 정점 중 가장 작은 간선 가중치를 갖는 정점을 선택하여 집합에 포함시킵니다.
- 집합의 정점 개수가 N이 될 때까지 2번을 반복합니다.
관련 문제
1197번: 최소 스패닝 트리
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이
www.acmicpc.net
'알고리즘 & 자료구조' 카테고리의 다른 글
| [알고리즘] 크루스칼 알고리즘 (Kruskal Algorithm), C++ (0) | 2024.01.01 |
|---|---|
| [알고리즘] 프림 알고리즘 (Prim's Algorithm), C++ (0) | 2023.12.10 |
| [알고리즘] TSP 외판원 순회 알고리즘 (1) | 2023.11.23 |
| [알고리즘] 희소 배열 (Sparse Table) (0) | 2023.11.10 |
| [자료구조] 세그먼트 트리 (Segment Tree) (0) | 2023.11.07 |
