다음 그래프로부터 생성되는 최소 비용 신장 트리(minimum cost… | [7급 국가직 자료구조론] 13년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 13년 1회차
다음 그래프로부터 생성되는 최소 비용 신장 트리(minimum cost spanning tree)의 비용은?
문제 이미지
1
31
2
32
3
34
4
42
해설

최소 비용 신장 트리의 비용은 32 이다.

크루스칼 알고리즘으로 가중치가 작은 간선부터 사이클이 생기지 않게 고르면 1, 2, 3, 4, 5 가 차례로 채택되고, 7 은 이미 연결된 정점끼리라 사이클이 생겨 제외된다. 가중치 8 간선 중에는 왼쪽 위와 맨 위 정점을 잇는 것만 채택되고, 마지막으로 9 를 넣어 정점 8 개를 간선 7 개로 모두 잇는다.

합계는 1+2+3+4+5+8+9=32 이다.

  • 31 : 최소 비용 32 보다 작아 어떤 신장 트리로도 만들 수 없다.
  • 34 : 왼쪽 정점을 잇는 데 9 대신 11 을 고르는 식으로 더 비싼 간선을 쓴 값이다.
  • 42 : 최소가 아닌 신장 트리의 비용이다.

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

이어서 풀어보기

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