ALGORITHM| Minimum Spanning Tree와 구현 알고리즘
in Blog / ALGORITHM on Mst, Kruskal, Prim
MST, Kruskal MST, Prim MST
최소 신장 트리(MST, Minimum Spanning Tree)란 Kruskal 알고리즘 이란 Prim 알고리즘 이란
Spanning Tree
그래프 내의 모든 정점을 포함하는 트리
- DFS, BFS를 이용하여 그래프에서 신장 트리(모든 노드가 사이클 없이 연결된 부분 그래프)를 찾을 수 있음
- 하나의 그래프에는 많은 신장 트리가 존재
- Spanning Tree는 트리의 특수한 형태로 모든 정점들이 연결, 사이클은 미포함
- Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결
MST(Minimum Spanning Tree) = 최소 신장 트리
최소 비용의 Spanning Tree를 선택하는 것으로 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것
- 간선의 가중치의 합이 최소
- n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야함
- 사이클이 포함되서는 안됨
구현 방법
Kruskal MST 알고리즘
greedy method를 이용하여 네트워크의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것
- MST가 최소 비용의 간선으로 구성, 사이클을 포함하지 않음의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 MST를 선택
- 간선 선택을 기반으로 하는 알고리즘
과정
- 그래프의 간선들을 가중치의 오름차순 정렬
- 정렬된 간선 리스트 중 순서대로 형성되지 않는 간선 선택
- 해당 간선을 현재의 MST의 집합에 추가
- 추가할 새로운 간선의 양끝 정점이 같은 집합에 속해 있으면 사이클이 형성됨
- 사이클 생성 여부를 확인하는 법
- 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 먼저 검사 -> Union-find 알고리즘
Prim MST 알고리즘
시간 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장
- 정점 선택을 기반
- 이전 단계에서 만들어진 트리 확장
과정
- 시작 단계에서는 시작 정점만이 MST 집합에 포함
- 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리 확장
- 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복
Kruskal VS Prim
union-find 알고리즘을 이용하면 Kruskal 알고리즘의 시간 복잡도는 간선들을 정렬하는 시간에 좌우됨
간선 e를 퀵 정렬과 같은 효율적인 알고리즘으로 정렬하면 Kruskal 알고리즘의 시간 복잡도는 $O(elog_2e)$
주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복하므로 Prim은 $O(n^2)$
Kruskal 알고리즘이 적합: 그래프 내에 적은 숫자의 간선만을 가지는 회소 그래프(Sparse Graph)의 경우
Prim 알고리즘이 적합: 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)의 경우
