<보기>의 그래프를 대상으로 최소신장트리(Minimum Sp… | [서울시 연구사 컴퓨터공학] 20년 1회차 기출문제 상세 페이지
1[서울시 연구사 컴퓨터공학] 20년 1회차
<보기>의 그래프를 대상으로 최소신장트리(Minimum Spanning Tree)를 만들고자 한다. 1번 노드부터 프림 알고리즘을 사용했을 때 간선(edge)을 선택하는 순서를 바르게 나열한 것은?<보기>
1
(1, 2) − (2, 4) − (4, 6) − (1, 3) − (3, 5) − (5, 7)
2
(1, 2) − (2, 4) − (4, 6) − (6, 7) − (5, 7) − (3, 5)
3
(1, 2) − (5, 7) − (4, 6) − (3, 5) − (2, 4) − (1, 3)
4
(5, 7) − (4, 6) − (1, 2) − (3, 5) − (2, 4) − (1, 3)
해설
프림 알고리즘은 이미 포함된 정점 집합에 인접한 간선 중 가중치가 가장 작은 것을 하나씩 추가하므로, 노드 1에서 시작하면 (1, 2) − (2, 4) − (4, 6) − (1, 3) − (3, 5) − (5, 7) 순서가 된다.
그림의 간선 가중치는 (1,2)=4, (1,3)=8, (1,6)=11, (2,3)=15, (2,4)=6, (2,6)=10, (4,6)=3, (4,5)=9, (3,5)=5, (5,7)=2, (6,7)=12 이다.
{1}에서 최소인 (1,2)=4 → {1,2}에서 (2,4)=6 → {1,2,4}에서 (4,6)=3 → {1,2,4,6}에서 (1,3)=8 → (3,5)=5 → 마지막으로 (5,7)=2 를 선택해 총 가중치 28의 트리가 완성된다.
- (4, 6) 다음에 (6, 7)을 고르는 순서: 그 시점에 (1,3)=8 이 (6,7)=12 보다 작으므로 프림 알고리즘의 선택이 아니며, 최종 트리도 최소가 아니다.
- (1, 2) 다음에 바로 (5, 7)을 고르는 순서: 그 시점에 정점 5·7은 트리에 인접하지 않으므로 프림 알고리즘으로는 선택될 수 없다.
- (5, 7)부터 시작하는 순서: 전체 간선을 가중치 오름차순으로 고른 크루스컬 알고리즘의 선택 순서이며, 노드 1에서 출발하는 프림의 순서가 아니다.
오류나 개정된 내용이 보이면 알려주세요
