다음 그림은 가중치 그래프이다. Kruskal 알고리즘을 이용하여 주어… | [9급 지방직 컴퓨터일반] 12년 1회차 기출문제 상세 페이지
1[9급 지방직 컴퓨터일반] 12년 1회차
다음 그림은 가중치 그래프이다. Kruskal 알고리즘을 이용하여 주어진 그래프의 최소비용 신장트리를 찾는 경우에 대한 설명으로 옳지 않은 것은?
1
최소비용 신장트리의 비용은 24이다.
2
최소비용 신장트리에 네 번째로 추가되는 간선은 V1과 V4를 연결한 것이다.
3
그래프에서 간선의 수가 n개일 때 알고리즘 시간 복잡도는 O(n2)이다.
4
새로운 간선을 추가할 때마다 사이클이 형성되는지 확인한다.
해설
옳지 않은 설명은 시간 복잡도가 O(n^2)라는 것이다. Kruskal 알고리즘은 간선 정렬이 지배하므로 간선 수가 n일 때 O(n log n)이다.
간선을 가중치 오름차순으로 V1-V2(2), V3-V4(3), V0-V2(4)를 넣고, V0-V1(5)은 사이클이라 버린 뒤 V1-V4(6), V3-V5(9)를 넣으면 신장트리가 완성된다.
- 최소비용 신장트리의 비용: 2 + 3 + 4 + 6 + 9 = 24로 옳다.
- 네 번째로 추가되는 간선: 가중치 5인 간선이 사이클로 제외되므로 네 번째는 V1과 V4를 잇는 가중치 6 간선이 맞다.
- 사이클 확인: 간선을 추가할 때마다 사이클 형성 여부를 검사하는 것이 Kruskal 알고리즘의 핵심 절차로 옳다.
내용에 오류가 있거나 최신 법령·기준과 다른 부분이 보이면 알려주세요. 확인 후 반영하겠습니다.