Prim 알고리즘을 사용하여 다음 가중 그래프(weighted grap… | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 18년 1회차
Prim 알고리즘을 사용하여 다음 가중 그래프(weighted graph)의 최소 비용 신장 트리(minimum cost spanning tree)를 구성할 때, 최소 비용과 마지막으로 선택되는 간선은? (단, 시작 정점은 A이다)
문제 이미지
1
42, (A, G)
2
43, (A, G)
3
44, (F, G)
4
45, (F, G)
해설

A에서 Prim 알고리즘을 적용하면 최소 비용은 42이고, 마지막으로 선택되는 간선은 (A, G)이다.

Prim 알고리즘은 이미 선택된 정점 집합과 나머지 정점을 잇는 간선 중 가중치가 가장 작은 간선을 하나씩 추가한다. 선택 순서는 (A, B) 10 → (B, C) 5 → (C, E) 3 → (E, F) 7 → (F, D) 6 → (A, G) 11 이다.

합계는 10+5+3+7+6+11=4210+5+3+7+6+11=42 이다. G는 (A, G) 11과 (F, G) 13으로만 연결되므로 마지막에 더 가벼운 (A, G)가 선택된다.

  • 43, (A, G): 마지막 간선은 맞지만 최소 비용은 42이다.
  • 44, (F, G): (F, G)는 가중치 13으로 (A, G)의 11보다 커서 신장 트리에 포함되지 않고, 비용도 42가 아니다.
  • 45, (F, G): 마지막 간선과 비용이 모두 계산 결과와 다르다.

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

이어서 풀어보기

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