2021. 6. 23. 18:41ㆍ알고리즘 공부
1. Spanning Tree란?
: 그래프 내의 모든 정점을 포함하는 트리를 뜻한다.
N개의 정점을 가지는 그래프의 최소 간선의 수는 N - 1개이고, N - 1개의 간선으로 연결되어 있으면 필연적으로 트리 형태를 갖게 되고 이것이 바로 Spanning Tree가 된다.
2. Spanning Tree의 특징
- DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다.(탐색 도중에 사용된 간선만 모으면 만들 수 있다.)
- 하나의 그래프에는 많은 신장 트리가 존재할 수 있다.
- Spanning Tree는 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안된다.
3. MST
: Minimum Spanning Tree의 약자로 간선의 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것을 의미한다.
- 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것은 아니다.
- 가중치를 간선에 할당한 그래프의 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이다.
4. MST의 구현 방법
4-1 ) Kruskal MST 알고리즘
: 그리디 알고리즘을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적의 해답을 구하는 것
- MST의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다.
- 간선 선택을 기반으로 하는 알고리즘이다.
- 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이다.
1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
- 가장 낮은 가중치를 먼저 선택한다.
- 사이클을 형성하는 간선을 제외한다.
3. 해당 간선을 현재의 MST의 집합에 추가한다.
4-2 ) Prim MST 알고리즘
: 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해 나가는 방법
- 정점 선택을 기반으로 하는 알고리즘이다.
- 이전 단계에서 만들어진 신장 트리를 확장하는 방법이다.
1. 시작 단계에서는 시작 정점만이 MST의 집합에 포함된다.
2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
- 즉, 가장 낮은 가중치를 먼저 선택한다.
3. 위 과정을 트리가 N-1개의 간선을 가질 때까지 반복한다.
참고 자료 : https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html