다음 가중 그래프(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 순으로 선택되며, 합은 이다.
- 비용을 13으로 본 조합은 최소 비용 계산이 틀렸다.
- (d, e)는 세 번째 단계에서 d, e 모두 아직 트리에 없어 선택될 수 없고, e가 들어온 뒤 네 번째로 선택된다.
오류나 개정된 내용이 보이면 알려주세요
