다음 그래프에서 각 간선에 가중치를 표시하였다. 이 가중치를 근거로 구… | [국회직 9급 컴퓨터일반] 19년 1회차 기출문제 상세 페이지

Kruskal 알고리즘으로 구성한 최소 비용 신장 트리의 총 가중치 합은 71이다.
Kruskal 알고리즘은 간선을 가중치 오름차순으로 살피며 사이클을 만들지 않는 간선만 고른다. 정점이 8개이므로 간선 7개를 고르면 끝난다.
채택 순서: 3(3-4), 4(1-3), 8(2-3), 9(4-6), 13(0-1), 16(4-5), 18(6-7)
사이클이 생겨 제외: 12(2-6), 15(0-2), 17(1-5)
7개를 다 골랐으므로 가중치 20인 5-7은 살피지 않는다.
$3+4+8+9+13+16+18=71$
67은 최소 비용인 71보다 작아 어떤 신장 트리로도 나올 수 없다.
69도 71보다 작아 신장 트리의 합이 될 수 없다.
73은 정점 7을 18이 아닌 20(5-7)으로 연결할 때의 합으로 최소가 아니다.
75는 정점 7을 20(5-7)으로, 정점 0을 13이 아닌 15(0-2)로 연결할 때의 합으로 최소가 아니다.