다음 그래프의 정점 A에서 시작하여 Prim 알고리즘을 적용하여 최소신… | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 15년 1회차
다음 그래프의 정점 A에서 시작하여 Prim 알고리즘을 적용하여 최소신장트리를 구축하고자 할 때, 설명으로 옳지 않은 것은?
1
우선순위 큐를 활용하여 구현한다.
2
탐욕(greedy) 기법을 이용한 알고리즘이다.
3
마지막으로 선택되는 정점은 G이다.
4
구축된 최소신장트리의 최소비용은 16이다.
해설
A에서 Prim 알고리즘을 적용하면 최소신장트리의 총비용은 17이므로, 최소비용이 16이라는 설명이 옳지 않다.
트리에 붙은 정점과 붙지 않은 정점을 잇는 간선 중 가장 가벼운 것을 매번 고르면 C(3) → F(3) → H(1) → E(2) → B(1) → D(4) → G(3) 순으로 정점이 추가된다.
총비용 = 3 + 3 + 1 + 2 + 1 + 4 + 3 = 17
- 우선순위 큐 활용: 후보 간선(또는 정점의 키 값) 중 최솟값을 반복해서 꺼내므로 우선순위 큐(힙)로 구현하는 것이 일반적이다.
- 탐욕 기법: 매 단계 현재 가장 작은 비용의 간선을 선택하는 탐욕(greedy) 알고리즘이다.
- 마지막 정점 G: 위 선택 순서에서 G는 D를 거쳐 비용 3으로 가장 마지막에 연결된다.
오류나 개정된 내용이 보이면 알려주세요
