최소 신장 트리?
- Spanning Tree = 신장 트리 = 스패닝 트리
- Spanning Tree는 그래프의 최소 연결 부분 그래프이다.
- 최소 연결 = 간선의 수가 가장 적다.
- n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결 되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다.
- 즉, 그래프에서 일부 간선을 선택해서 만든 트리
특징
- DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다.
- 탐색 도중에 사용된 간선만 모으면 만들 수 있다.
- 하나의 그래프에는 많은 신장 트리가 존재 할 수 있다.
- Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안 된다.
- 그래프에 있는 n개의 정점을 정확히 n-1개의 간선으로 연결 한다.
쓰이는 곳
- 통신 네트워크 구축?
MST(Minimum Spanning Tree)
- 최소 신장 트리
- Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리
- 간선의 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것!
- 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것!
특징
- 간선의 가중치 합이 최소여야 한다.
- n개의 정점을 가지는 그래프에 대해 반드시 n-1개의 간선만을 사용해야 한다.
- 사이클이 포함되어서는 안 된다.
MST의 사용 사례
- 통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우
MST 구현 방법
1. Kruskal MST 알고리즘
탐욕적인 방법 = 그리디 를 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것.
- MST(최소 비용 신장 트리)가 1) 최소 비용의 간선으로 구성 2)사이클을 포함하지 않음 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선 선택.
- 간선 선택을 기반으로 하는 알고리즘
- 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법
[과정]
1. 그래프의 간선들을 가중치의 오름차순으로 정렬
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
- 즉, 가장 낮은 가중치 먼저 선택
- 사이클을 형성하는 간선을 제외.
3. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가
Kruskal 알고리즘의 시간 복잡도
- union-find 알고리즘을 이용하면 Kruskal 알고리즘의 시간 복잡도는 간선들을 정렬하는 시간에 좌우된다.
- 즉, 간선 e개를 퀵 정렬과 같은 효율적인 알고리즘으로 정렬한다면
- Kruskal 알고리즘의 시간 복잡도는 O(eloge)가 된다. - Prim의 알고리즘의 시간 복잡도는 O(n^2)이므로
- 그래프 내에 적은 숫자의 간선만을 가지는 '희소 그래프'의 경우 Kruskal 알고리즘이 적합하고- 그래프에 간선이 많이 존재하는 '밀집 그래프'의 경우는 Prim 알고리즘'이 적합하다.
프림 알고리즘
- 시작 정점을 선택하고서 정점에 인접한 간선 중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식.
Kruskal Algoritm vs Prim Algritm
- 둘 다 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞에 보이는 최소 비용 선택으로 최적의 솔루션을 찾음)
- 크루스칼 알고리즘은 전체 간선 중에서, 가장 가중치가 작은 간선부터 선택하면서 MST를 구함
- 프림 알고리즘은 특정 정점에서 시작, 해당 정점에 연결된 가장 가중치가 작은 간선을 선택, 간선으로 연결된 정점들에 연결된 간선 중에서 가장 가중치가 작은 간선을 택하는 방식!
관련 알고리즘 문제
developer