Today I Learned
오늘은 그리디 알고리즘 문제를 풀다가 본 최소신장트리의 개념에 대해 정리해보고자 한다.
참고 사이트 : gmlwjd9405
Spanning Tree
신장트리, 그래프의 모든 정점을 포함하는 트리로 최소 연결 부분 그래프.
-
최소 연결 : 간선의 수가 가장 적다.
-
N개의 정점을 가질 때 정점이 모두 연결되는 최소 간선 수는 N-1로 무조건 트리 형태가 되는데 이 트리를 신장트리라 한다.
-
하나의 그래프에는 많은 신장트리가 존재한다.
-
모든 정점이 연결되어있어야 하지만 Cycle(원형으로 계속 순회)이 되면 안된다.
MST(Minimum Spanning Tree)
최소신장트리, Spanning Tree 중에서 사용된 간선의 가중치의 합이 가장 적은 트리
-
네트워크에 있는 모든 정점을 가장 적은 수의 간선과 비용(가중치)로 연결하는 것
-
조건 :
Cycle이 되면 안된다.
n-1개의 간선만 사용해 모든 N개의 정점을 연결해야한다.
간선의 가중치의 합이 최소여야한다.
MST 구현 방법
Kruskal Algorithm
간선을 기준으로 MST를 형성하는 알고리즘
이미지 출처 : gmlwjd9405
-
가중치가 적은 간선부터 선택해나가는 방식
-
Greedy방식을 사용해 순간순간의 최적 해를 선택해나가는 방식이다. Kruskal 알고리즘은 이런 Greedy방식을 사용해도 전체의 최적해가 된다는 것이 이미 증명되어 있다.
-
그래프의 간선을 오름차순으로 정렬해 사이클을 형성하는 간선을 제외하고 가장 적은 가중치의 간선을 차례대로 선택해나간다.
-
이전 단계로 형성된 신장트리는 전혀 생각하지 않고 사이클 형성 여부만 본 채 최소비용의 간선을 선택해나가는 방법
-
사이클 생성 여부는 Union-Find 알고리즘을 통해 확인한다.(TIL #155에 정리 예정)
-
시간복잡도는 간선의 수를 E, 정점의 수를 V라 하면,
먼저 간선을 오름차순으로 정렬할 때 효율적인 정렬 알고리즘을 사용하면 O(E log E).
Union-Find 알고리즘에 O(E log V).
따라서 최악의 경우 시간복잡도는 O(E log E) or O(E log V)이다.
Prim Algorithm
정점을 기준으로 MST를 형성하는 알고리즘
이미지 출처 : gmlwjd9405
-
시작정점에서 부터 신장 트리를 점점 확장해나가는 방식
-
정점 하나를 골라 가장 가중치가 적은 간선을 고르고 다음 정점으로 이동.
-
앞단계에서 형성된 MST집합을 가중치가 작은 간선을 성택해 정점을 연결해나가는 방식. 모든 정점을 방문하면 MST가 형성된다.
-
시간복잡도는 인접행렬과 선형검색을 사용하면 정점 수 V에 대해 O(V^2).
하지만 최소 힙(우선순위 큐)를 사용하면 간선 수 E와 정점 수 V에 대해 O(E log V).
두 알고리즘의 선택 기준
-
일반적으로 간선의 수가 정점에 비해 적은
희소그래프의 경우 Kruskal이 더 유리하다.
간선을 정렬하는 시간에 O(E log E)가 소모되기 때문에 간선이 적으면 더 빠르다. -
반면 간선의 수가 정점의 수와 비슷한
밀집그래프의 경우 Prim이 더 유리하다.
각 단계에서 최소 가중치의 간선을 선택하는 방식으로 동작하기 때문에 O(E log V)이고, 크루스칼은 정렬에 시간이 더 소모되기 때문이다.
