다음 그래프를 대상으로 크루스칼(Kruskal) 알고리즘을 적용하여 최… | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 25년 1회차
다음 그래프를 대상으로 크루스칼(Kruskal) 알고리즘을 적용하여 최소 신장 트리(MST, Minimum Spanning Tree)를 구성하고자 할 때, 생성되는 MST에 5번째 추가되는 간선과 비용을 바르게 연결한 것은?
1
간선 (b, c) / 비용 16
2
간선 (d, g) / 비용 18
3
간선 (d, e) / 비용 22
4
간선 (e, g) / 비용 25
해설
5번째로 추가되는 간선은 (d, e), 비용 22이다.
크루스칼 알고리즘은 간선을 비용 오름차순으로 검사해 사이클을 만들지 않는 간선만 채택한다. 순서대로 (a, f) 10, (c, d) 12, (b, g) 15, (b, c) 16이 채택된다.
다음 (d, g) 18은 이미 g-b-c-d로 연결된 두 정점을 잇게 되어 사이클이 생기므로 버려지고, 이어지는 (d, e) 22가 다섯 번째로 채택된다.
- (b, c) 비용 16: 네 번째로 채택되는 간선이다.
- (d, g) 비용 18: 사이클을 형성해 MST에 포함되지 않는다.
- (e, g) 비용 25: e가 이미 d를 통해 연결된 뒤라 사이클이 생겨 제외된다.
오류나 개정된 내용이 보이면 알려주세요