트리(Tree)
- 그래프의 특수한 경우.
- 사이클이 없이 모든 정점이 연결되어 있는 그래프.
- 2개의 노드 사이에 반드시 1개의 간선만을 가짐.
- 부모-자식 관계가 존재하여 계층형 모델이라고도 함. 최상위에 Root 노드 존재.
스패닝 트리(Spanning Tree)
- 그래프 내의 모든 정점을 포함하는 트리
- 그래프의 최소 연결 그래프.
그러므로 간선의 개수는 (V-1)개 (V는 정점의 개수) - 스패닝 트리 = 신장 트리
최소 스패닝 트리(MST, Minimum Spanning Tree)
- 스패닝 트리 중 간선 가중치의 합이 최소가 되는 스패닝 트리
- MST를 구하는 알고리즘은 보통 아래의 2가지를 많이 사용
- 크루스칼 알고리즘 (Kruskal Algorithm)
- 프림 알고리즘 (Prim Algorithm)
크루스칼 알고리즘 (Kruskal Algorithm)
- 선택되지 않은 간선 중 최소 가중치를 갖는 간선을 선택해가며 MST를 만드는 알고리즘
- 그리디 알고리즘
- 간선 선택을 기반으로 하는 알고리즘
- 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택
- 동작 원리
- 간선들의 가중치를 오름차순 정렬
- 선택되지 않은 간선 중 최소 가중치를 갖는 간선 선택
- 이 간선을 선택했을 때 사이클이 발생한다면 선택하지 않음. 사이클이 발생하는지 확인하는데에는 Union-find 알고리즘 이용.
- 총 (V-1)개의 간선이 선택될 때까지 반복.
- 시간 복잡도 : $O(Elog_2E)$
Union-find 알고리즘은 시간복잡도가 $O(1)$, 즉 상수 시간 복잡도를 가지므로 모든 간선 E개을 오름차순 정렬하는데 걸리는 시간인 $O(ElogE)가 전체 시간 복잡도를 결정하게 된다.
프림 알고리즘 (Prim Algorithm)
- 한 정점에서 시작하여 스패닝 트리 집합을 단계적으로 확장해나가는 방법
- 정점 선택을 기반으로 하는 알고리즘
- 이전 단계에서 만들어진 신장 트리를 확장하는 방법
- 프림 알고리즘은 항상 이전 단계에서 만들어진 신장 트리 집합 밖에 있는 정점을 선택하기 때문에 사이클을 형성하지 않는다.
- 동작 원리
- 임의의 시작 정점을 선택하여 MST 집합에 포함
- MST 집합에 포함된 정점들에 인접한 정점들 중 최소 가중치를 갖는 정점을 선택.
- 총 (V-1)개의 간선이 선택될 때까지 2번 과정을 반복
- 시간 복잡도 : $O(V^2)$
매번 V개의 정점이 V개의 정점에 대해 탐색을 진행하기 때문이다. - 최소 힙을 사용하는 경우 시간 복잡도 : $O(ElogV)$
최소 가중치를 갖는 정점을 선택할 때 그냥 배열이 아닌 최소 힙을 사용하면 시간 복잡도를 줄일 수 있다.
크루스칼 vs 프림
크루스칼의 시간 복잡도는 $O(Elog_2E)$, 프림의 시간 복잡도는 $O(ElogV)$이다.
그러므로 그래프 내의 간선이 적은 Sparse Graph는 크루스칼, 간선이 많은 Dense Graph는 프림이 유리하다.
[참고]
https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html#google_vignette
'CS > 알고리즘' 카테고리의 다른 글
최단 경로 알고리즘 (0) | 2023.04.03 |
---|---|
피보나치 수열 (0) | 2023.02.10 |
순열과 조합 (0) | 2023.02.10 |
에라토스테네스의 체 (소수 판별 알고리즘) (0) | 2023.02.05 |
효율적으로 약수 구하기 (0) | 2023.02.04 |