다음 가중 그래프(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개가 되어 완성된다.
2+3+4+4+5+6+7+8=392+3+4+4+5+6+7+8=39

  • 36 — 최소 합 39보다 작아, 사이클 없이 9개 정점을 모두 잇는 방법으로는 얻을 수 없다.
  • 44 — D-G(4) 대신 E-G(9)로 G를 연결한 신장 트리의 비용으로, 최소가 아니다.
  • 46 — 최소 비용보다 큰 값으로, 더 무거운 간선을 포함한 신장 트리의 비용이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 20년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기