최소 신장 트리(MST)
- 그래프에서 최소 비용 문제
- 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
- 두 정점 사이의 최소 비용의 경로 찾기
- 신장 트리
- n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리
- 최소 신장 트리(Minimun Spaning Tree)
- 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리
KRUSKAL 알고리즘 (크루스칼 알고리즘 - O(E log V))
- 간선을 하나씩 선택해서 MST를 찾는 알고리즘
- 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬
- 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가 시킴.
→ 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택 - n-1개의 간선이 선택될 때까지 2를 반복
PRIM 알고리즘 (프림 알고리즘 - O(E log V))
- 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식
- 임의 정점을 하나 선택해서 시작
- 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
- 모든 정점이 선택될 때까지 1, 2 과정을 반복
- 서로소인 2개 집합 정보를 유지 ( 굳이 나누자면 이와 같이 나눔, 그냥 선택 비선택으로 생각)
- 트리 정점들 - MST를 만들기 위해 선택된 정점들
- 비트리 정점들 - 선택되지 않은 정점들
'Algorithms > 개념 정리' 카테고리의 다른 글
[문자열] 문자열 패턴 매칭 (0) | 2021.04.06 |
---|---|
[Graph] 최단 경로 (0) | 2021.03.30 |
[Graph] 서로소 집합 (0) | 2021.03.26 |
[Graph] Graph 탐색 (0) | 2021.03.25 |
[Graph] Graph 이론 (0) | 2021.03.24 |