다음 가중 그래프(weighted graph)에서 최소 비용 신장 트리… | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 14년 1회차
다음 가중 그래프(weighted graph)에서 최소 비용 신장 트리(minimum spanning tree)를 얻기 위해 노드 a에서 시작하여 Prim 알고리즘을 적용할 때 신장 트리의 최소 비용과 세 번째로 선택된 간선을 순서대로 나열한 것은?
문제 이미지
1
12, (b, e)
2
13, (b, e)
3
12, (d, e)
4
13, (d, e)
해설

최소 비용은 12이고 세 번째로 선택되는 간선은 (b, e)이다.

Prim 알고리즘은 이미 트리에 포함된 정점에서 나가는 간선 중 가장 가벼운 것을 하나씩 추가한다.

a에서 (a, b) 2 → (b, f) 1 → (b, e) 3 → (e, d) 2 → (b, c) 4 순으로 선택되며, 합은 2+1+3+2+4=122+1+3+2+4=12이다.

  • 비용을 13으로 본 조합은 최소 비용 계산이 틀렸다.
  • (d, e)는 세 번째 단계에서 d, e 모두 아직 트리에 없어 선택될 수 없고, e가 들어온 뒤 네 번째로 선택된다.

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

이어서 풀어보기

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