[TIL] 최소 신장 트리 MST, Minimum Spanning Tree
최소 신장 트리 MST, Minimum Spanning Tree
가중치가 있는 연결 그래프에서 모든 정점을 연결하는 간선들의 부분 집합 중에
간선들의 가중치 합이 최소가 되는 트리
즉, 스패닝 트리 중 간선의 가중치 합이 최소인 트리
스패닝 트리 Spanning Tree
그래프 내의 모든 정점을 포함하는, 그래프의 최소 연결 부분 그래프
n 개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1) 이고,
(n-1) 개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 된다 -> 스패닝 트리!
MST 특징
1. n 개의 정점을 가지는 그래프에서 최소 신장 트리는 n-1 개의 간선을 가진다
(단, 모든 정점이 반드시 연결된 경우에만 성립하며, 가중치가 음수인 경우는 해당되지 않는다)
2. 사이클이 없고 모든 정점이 연결되어 있다
3. 간선의 가중치 합이 최소이다
MST 사용 예시
최소한 비용으로 모든 지점을 연결해야 하는 문제에 자주 사용된다
ex. 도시마다 도로를 짓는데 최소 거리가 되도록 구축
마을에 전화망을 설치하는데 최소 비용이 되도록 설계
MST 알고리즘
크루스칼 Kruskal 알고리즘
간선 중심 알고리즘
모든 간선을 가중치 순으로 오름차순 정렬하고
가장 작은 가중치부터 사이클을 만들지 않는 간선을 선택해 나가면서 트리를 구성한다
유니온-파인드 Union-Find 알고리즘을 사용하여 사이클을 방지한다
시간 복잡도는 보통 O(ElogE) 이지만 간선이 많은 경우 O(ElogV) 로도 표현할 수 있다 (V 정점 E 간선)
유니온 파인드 Union-Find 알고리즘
여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어 주고,
어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘
상호 배타적 집합, 서로소 집합 Disjoin-set 이라고도 부른다
각 그룹을 트리의 형태로 표현하고, 최상위 노드인 Root 를 통해 그룹을 구별한다
프림 Prim's 알고리즘
정점 중심 알고리즘
시작 정점에서부터 출발하여 현재 선택된 정점과 연결된 간선 중에서
가장 작은 가중치를 가지는 간선을 선택하면서 트리를 확장한다
시간 복잡도는 보통 O((V+E)logV) 이지만
힙 (우선순위 큐) 을 사용하면 O(ElogV) 로도 표현할 수 있다 (V 정점 E 간선)
크루스칼과 프림 비교
| 크루스칼 | 프림 |
| 간선 중심 알고리즘 | 정점 중심 알고리즘 |
| 사이클이 이루어지는지 확인 필요 | 사이클을 이루지 않음 |
| 간선의 개수가 작을 때 유용 | 간선의 개수가 많을 때 사용 |
| 간선을 기준으로 정렬하는 과정이 오래 걸림 | 최소 거리의 정점 찾는 부분이 오래 걸림 |