최소 스패닝 트리 (Minimum Spanning Tree, MST)

참고 블로그 : https://www.crocus.co.kr/733

정의 :
 - 그래프에서 그래프의 모든 정점을 연결하되, 사이클이 존재하지 않도록 모든 정점을 간선으로 연결하는 것을 의미
 - 최소 스패닝 트리는 무조건 하나의 그래프에서 하나만 생성된다고는 보장하지는 못한다.

최소 스패닝 트리 알고리즘

1. 크루스칼 알고리즘
- 모든 간선에 대해 가장 가중치가 작은 간선부터 연결해주면서 최소 스패닝 트리를 만들어 나가는 알고리즘을 의미
- 크루스칼 알고리즘 자체가 유니온 파인드 자료구조 기반으로 생성된다
--> 유니온 파인드 자료구조를 공부한 경험이 있으나, 위에 참고한 블로그에서는 더 쉽고, 자세히 설명되어있어 다시 게시글을 올릴예정
- 크루스칼 알고리즘의 시간 복잡도 : O(ElogE)

2. 프림 알고리즘
- 하나의 시작점을 잡고 시작점과 연결된 정점들에 대해 가장 가중치가 작은 간선부터 연결해주면서 최소 스패닝 트리를 만들어 나가는 알고리즘
- 연결하는 도중 사이클이 생기게 된다면 가중치가 작은 간선이어도 무시
- 우선순위 큐를 기반으로 제작
- 프림 알고리즘의 시간 복잡도 : O(ElogV)

3. 크루스칼 알고리즘 vs 프림 알고리즘
- 간선의 개수가 작은 경우에는 크루스칼 알고리즘,
- 간선의 개수가 많은 경우에는 프림 알고리즘

최소 스패닝 트리 문제 링크 : https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리