1197 최소 스패닝 트리

주어진 그래프의 최소 스패닝 트리를 구하는 문제이다.
최소 스패닝 트리는 모든 간선을 연결하는 트리중 가중치의 합이 가장 작은것을 말한다.

나는 그래프 알고리즘중에 최소 소패닝트리를 구축하는 알고리즘중 하나인 프림 알고리즘을 이용하여 문제를 해결했다. 프림 알고리즘은 힙구조를 사용할 때 O(E*log(V))의 시간복잡도를 보인다. 여기서 V는 정점의 수이고, E는 간선의 수를 말한다.
그런데 상당히 느린 결과가 나왔다.

다른 사람이 해결한 방법을보니 정렬을 이용하여 해결해주었다.

그래프문제를 항상 그래프 알고리즘으로만 생각하는 버릇을 고쳐야겠다.

소스