신장트리란?
하나의 그래프가 있을 때 모든 노드를 포함하면서 간선의 가중치 합이 최소가 되는 신장 트리를 MST라고 한다. 사이클이 존재하지 않는 부분 그래프
✨MST(Minimum Spanning Tree)
1. MST는 그리디 알고리즘 이다.
각 시점에서 최선의 것을 선택하기 때문에 그리디 알고리즘 이지만, 그리디 알고리즘은 최적의 답을 찾아주는 대신 문제에 따라서는 그렇지 않은 경우도 있다. 또한, 제일 작은 간선이 여러개일 경우 선택하는 값마다 경로가 달라진다.
2. 노드 N개에 대해서 간선의 수가 N-1개이다.
3. MST 종류
- 크루스칼
- 프림
1. 크루스칼 알고리즘
- 간선을 오름차순 정렬한다.
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.(UnionFind)
2-1. 사이클이 발생하지 않는 경우에만 최소 신장 트리에 포함한다. - 모든 간선에 대해서 2번의 과정을 반복한다.
2. 프림 알고리즘
✨임의의 시작점에서 PriorityQueue에 연결된 간선의 정보를 담아서 구현하는 알고리즘.
시간 복잡도
E : 간선 개수
V : 노드 개수
크루스칼 : O(ElogE)
프림 : O(ElogV)
간선(E)가 많은 경우 프림 유리! 아니면 크루스칼!
Hi!