다음 그래프에 대하여 Sollin 알고리즘으로 최소 비용 신장 트리를 … | [7급 국가직 자료구조론] 22년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 22년 1회차
다음 그래프에 대하여 Sollin 알고리즘으로 최소 비용 신장 트리를 구하고자 한다. 각 노드가 하나의 트리로 구성된 초기 상태에서 한 단계 처리한 이후의 결과로 두 개의 트리로 구성된 포리스트(forest)가 만들어졌을 때, 각 트리의 가중치 합 중 큰 값은?
1
9
2
12
3
13
4
16
해설
한 단계 처리 후 두 트리의 가중치 합은 9와 16이므로 큰 값은 16이다.
Sollin 알고리즘은 각 트리(초기에는 각 노드)가 자신에 연결된 최소 가중치 간선을 하나씩 동시에 선택한다. A는 A-B(6), B와 E는 B-E(3), C와 D는 C-D(4), F는 F-C(5), G는 G-F(7)를 고른다.
그 결과 A-B-E 트리(6+3=9)와 C-D-F-G 트리(4+5+7=16)의 두 트리로 된 포리스트가 만들어진다.
- 9는 두 트리 중 작은 쪽인 A-B-E 트리의 가중치 합이다.
- 12는 D-F 간선의 가중치로, 각 노드의 최소 간선이 아니어서 이 단계에서 선택되지 않는다.
- 13은 어느 트리의 합과도 맞지 않는 값이다.
오류나 개정된 내용이 보이면 알려주세요