[알고리즘]MST 최소 신장 트리 알고리즘 - Kruskal & Prim
[ Spanning Tree ]
Spanning Tree(신장 트리)는 그래프 내의 모든 정점을 포함하는 트리입니다.
그래프의 n 개의 정점을 모두 연결하는 최소 간선의 수는 (n-1) 개이고, 이때 이루어진 그래프를 최소 연결 부분 그래프, 즉 Spanning Tree라고 합니다.
즉, 그래프에서 일부 간선을 선택해서 만든 트리입니다.
- Spanning Tree 특징
- DFS, BFS를 이용하여 그래프의 신장 트리를 찾을 수 있다.
- 하나의 그래프에는 많은 신장 트리가 존재할 수 있다.
- 신장 트리는 모든 정점들이 연결되어 있어야 한다.
- 신장 트리는 사이클을 포함해서는 안된다.
- 신장 트리는 n 개의 정점과 (n-1) 개의 간선으로 이루어져 있다.
[ MST 최소 신장 트리 ]
최소 신장 트리(MST, minimum spanning tree)는 Spanning Tree 중에서 간선들의 가중치 합이 최소인 트리입니다.
즉, 그래프의 모든 정점을 연결한 그래프 중 연결된 간선의 가중치 합이 최소인 신장 트리입니다.
- MST 특징
- 간선의 가중치 합이 최소
- n 개의 정점과 (n-1) 개의 간선
- 사이클이 포함되선 안됨
MST 를 구현하는 알고리즘에는 Kruskal MST 알고리즘과 Prim MST 알고리즘이 있습니다.
[ Kruskal MST 알고리즘 ]
Kruskal MST 알고리즘은 그리디 알고리즘을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 알고리즘입니다.
간선 선택을 기반으로 하는 알고리즘입니다.
- 알고리즘
1. 그래프의 간선들을 가중치의 오름차순으로 정렬 -> 최소 힙으로 구현
2. 각 정점은 자기 자신만을 정점으로 갖는 트리를 구성한다.
- 각 정점의 root 정점은 자기 자신으로 초기화
3. 최소 힙(간선 리스트)에서 첫 번째 간선(가중치가 최소인)을 pop
4. 해당 간선이 사이클을 발생시키는지 확인
- 해당 간선에 양 끝 정점의 root 정점을 찾는다.(find)
- 두 root 정점이 갖다면, 사이클을 발생시키므로 2단계로 돌아간다.
- 두 root 정점이 다르다면, 한 정점의 root 정점을 다른 한 정점의 root 정점으로 갱신한다.(union)
5. 최소 신장 트리에 해당 간선의 정보 추가
6. 최소 힙(간선 리스트)가 empty일 때까지 3~5 과정 반복
[ Prim MST 알고리즘 ]
Prim MST 알고리즘은 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법입니다.
정점 선택을 기반으로 하는 알고리즘으로 BFS와 유사합니다.
- 알고리즘
1. 시작 정점을 MST 에 추가한다.
2. 시작 정점에 대한 정보를 최소 힙(우선순위큐)에 추가한다. (가중치 오름차순)
- 최소 힙: MST 를 찾을 자료구조
3. 힙에서 정점을 pop 한다.
4. 해당 정점이 이미 방문한 정점이라면 3단계로 돌아간다.
5. 방문하지 않은 정점이라면, MST 에 해당 정점의 정보를 추가한다.
6. 방문 표시 후 해당 정점에 연결된 정점과 그 가중치를 최소 힙에 추가한다.
7. 최소 힙이 empty 일 때까지 3~6 과정을 반복한다.