궤도

문제 풀이 최소 신장 트리, 최소 스패닝 트리, MST 등등으로 불리는 문제다. 가중치가 있는 간선이 주어진 그래프가 있을 때 가중치의 합이 가장 작은 트리를 만드는 것인데 트리니까 당연히 사이클이 없을 것이고 정점의 수가 V일 때, 최종 간선의 수는 V-1이 될 것이다. 이러한 MST를 만드는 대표적인 알고리즘은 크루스칼과 프림이 있는데 크루스칼(kruskal)은 유니온 파인드를 이용해 푸는 알고리즘이고 프림은 다익스트라랑 비슷해보여서 많이들 헷갈리지만 아무튼 둘은 다른 알고리즘이다. ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 크러스컬 알고리즘 - 위키백과, 우리 모두의 백과..