다음 가중치 그래프에 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)를 고른다.
2+1+3+2+4=122+1+3+2+4=12
12+3=1512+3=15

  • 13 — 세 번째 간선을 1로 잘못 잡은 경우의 값이다.
  • 14 — 세 번째 간선을 2로 잘못 잡은 경우의 값이다.
  • 16 — 세 번째 간선을 4로 보거나 C를 C-F(5)로 연결한 경우의 값이다.

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

이어서 풀어보기

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