다음 그림은 가중치 그래프이다. Kruskal 알고리즘을 이용하여 주어진 그래프의 최소비용 신장트리를 찾는 경우에 대한 설명으로 옳지 않은 것은?
- ①최소비용 신장트리의 비용은 24이다.
- ②최소비용 신장트리에 네 번째로 추가되는 간선은 V1과 V4를 연결한 것이다.
- ③그래프에서 간선의 수가 n개일 때 알고리즘 시간 복잡도는 O(n2)이다.
- ④새로운 간선을 추가할 때마다 사이클이 형성되는지 확인한다.
선지를 골라 바로 채점해 보세요.
정답 ③
출처: 인사혁신처 공개 기출(공공데이터포털, 이용허락 제한 없음)