다음 가중치 그래프에 Prim 알고리즘을 적용하여 최소 비용 신장 트리… | [7급 국가직 자료구조론] 20년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 20년 1회차
다음 가중치 그래프에 Prim 알고리즘을 적용하여 최소 비용 신장 트리(minimum cost spanning tree)를 만들 때, 최소 비용과 세 번째로 선택된 간선의 가중치의 합은? (단, A를 시작 정점으로 한다)
1
13
2
14
3
15
4
16
해설
최소 비용 12와 세 번째 간선 가중치 3을 더한 15가 답이다.
Prim 알고리즘은 현재 트리에 인접한 간선 중 최소 가중치를 하나씩 추가한다. A에서 A-B(2), 이어서 B-F(1), 그다음 후보 중 최소인 B-E(3)가 세 번째로 선택된다.
이후 E-D(2), 마지막으로 C를 잇는 B-C(4)를 고른다.
- 13 — 세 번째 간선을 1로 잘못 잡은 경우의 값이다.
- 14 — 세 번째 간선을 2로 잘못 잡은 경우의 값이다.
- 16 — 세 번째 간선을 4로 보거나 C를 C-F(5)로 연결한 경우의 값이다.
오류나 개정된 내용이 보이면 알려주세요
