최소 신장 트리에 대해 설명하세요
Keyword
신장 트리, cycle, edge weight, Kruskal, Prim
Script
먼저 신장 트리(spanning tree)는 원 그래프 기준으로 모든 정점이 cycle 없이 연결된 형태를 말합니다. 이 신장 트리는 여러개가 존재할 수 있는데, 그 중 간선의 가중치의 합이 가장 최소가 되는 신장 트리를 최소 신장 트리(Minimum Spanning Tree)라고 합니다.
최소 신장트리를 찾는 알고리즘으로 대표적으로 Kruskal 알고리즘과 Prim 알고리즘이 존재합니다.
Additional
Kruskal Algorithm
대표적인 최소 신장 트리 탐색 알고리즘으로, 기본적으로 그리디 기법을 기반으로 한다. 모든 간선에 대해서, 가중치가 가장 최소가 되는 간선 순으로 정점 사이를 차례대로 이어나가며 cycle이 발생하는 경우는 건너뛰고 모든 정점이 연결될 때까지 반복적으로 수행한다.
시간복잡도는
- 정렬 수행에 O(ElogE)
- cycle 탐지를 위한 union-find에 O(1)
로 총 O(ElogE)의 시간복잡도로 수행된다.
Prim Algorithm
Prim 알고리즘도 Kruskal과 마찬가지로 기본적으로 그리디 기법을 기반으로 한다. Kruskal과 다르게 시작 노드를 임의로 정하고 해당 노드부터 뻗어나가는 전략이다.
- 먼저 임의로 노드 하나를 선택하여 MST 집합에 넣는다.
- 현재 MST 집합에 속한 정점들과 인접한 정점 중, 아직 MST 집합에 속하지 않은 정점과의 간선들을 모두 우선순위 큐에 넣는다.
- 이 중 가장 작은 가중치를 가지는 것을 큐에서 꺼내고, 연결된 정점은 MST 집합에 포함시킨다.
- 이 과정을 MST 집합에 모든 정점이 포함될 때까지 반복한다.
시간복잡도는
- 모든 노드 탐색에 O(V)
- 우선순위 큐를 이용한 탐색에는 전체 O(VlogV)
- 각 인접 간선 탐색에 O(E)
- 우선순위 큐 구성에 전체 O(ElogV)
로 총 O(VlogV + ElogV) => O(ElogV) (일반적으로 E가 V보다 큼)
with programming