다음 비용 그래프에서 최소 비용 신장 트리를 구하고자 한다. Prim … | [7급 국가직 자료구조론] 11년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 11년 1회차
다음 비용 그래프에서 최소 비용 신장 트리를 구하고자 한다. Prim 알고리즘을 이용하여 최소 비용 신장 트리를 구할 때, 4번째로 연결되는 간선(edge)으로 옳은 것은? (단, 시작 노드는 A이다)
1
(A, D)
2
(B, E)
3
(E, F)
4
(F, C)
해설
A에서 시작한 Prim 알고리즘의 네 번째 간선은 (E, F)이다.
Prim은 이미 선택된 정점 집합과 바깥 정점을 잇는 간선 중 최소 비용 간선을 하나씩 추가한다. 선택 순서는 (A, B) 5 → (B, E) 20 → (E, D) 10 → (E, F) 30 이다.
- (A, B) 5: 첫 번째로 연결되는 간선이다.
- (B, E) 20: 두 번째로 연결되는 간선이다.
- (A, D): D는 세 번째 단계에서 더 싼 (E, D) 10으로 연결되므로 선택되지 않는다.
- (F, C) 15: F가 들어온 다음인 다섯 번째에 연결되는 간선이다.
오류나 개정된 내용이 보이면 알려주세요
