다음 가중 그래프(weighted graph)에 Kruskal 알고리즘… | [7급 국가직 자료구조론] 20년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 20년 1회차
다음 가중 그래프(weighted graph)에 Kruskal 알고리즘을 적용하여 구성한 최소 비용 신장 트리(minimum cost spanning tree)의 최소 비용은?
1
36
2
39
3
44
4
46
해설
Kruskal 알고리즘으로 구한 최소 비용 신장 트리의 비용은 39이다.
가중치가 작은 간선부터 고르되 사이클을 만드는 간선은 버린다. A-B(2), A-C(3), C-D(4), D-G(4)를 고른 뒤 B-D(5)는 A-B-D-C 사이클을 만들어 제외한다.
이어서 G-I(5), D-H(6), B-E(7), H-F(8)를 고르면 정점 9개에 간선 8개가 되어 완성된다.
- 36 — 최소 합 39보다 작아, 사이클 없이 9개 정점을 모두 잇는 방법으로는 얻을 수 없다.
- 44 — D-G(4) 대신 E-G(9)로 G를 연결한 신장 트리의 비용으로, 최소가 아니다.
- 46 — 최소 비용보다 큰 값으로, 더 무거운 간선을 포함한 신장 트리의 비용이다.
오류나 개정된 내용이 보이면 알려주세요
