그래프가 주어졌을 때, 모든 정점과 간선의 일부만으로 구성한 트리를 스패닝 트리라고 한다. 이 중에서 간선 가중치의 총합이 가장 작은 트리를 최소 스패닝 트리(Minimum Spanning Tree) 라고 한다. MST를 구하는 알고리즘은 2가지가 있다. 프림 알고리즘과 크루스칼 알고리즘이다. 프림(Prim) 알고리즘 프림 알고리즘은 BFS 와 유사한 방식으로 진행되며, 최초 임의의 정점을 MST에 추가한 뒤, 아직 MST에 포함되지 않은 정점을 연결하는 간선 중 최소인 간선을 MST에 추가하는 방식이다. 우선순위 큐를 이용해서 구현하면 O(ElogE) 의 시간복잡도를 갖는다. https://www.acmicpc.net/problem/1922 package mst.프림.네트워크연결; import java..