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 이다.
합계는 이다. 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): 마지막 간선과 비용이 모두 계산 결과와 다르다.
오류나 개정된 내용이 보이면 알려주세요
