다음 그래프에서 크루스칼 알고리즘(Kruskal algorithm)을 … | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지

크루스칼 알고리즘으로 만든 최소 비용 신장 트리의 가중치 합은 25이다.
간선을 가중치 오름차순으로 보며 사이클을 만들지 않는 것만 고르면 A-B(3), A-C(4), A-E(4), F-G(4), A-D(5), E-G(5)로 정점 7개를 잇는 간선 6개가 완성된다.
3+4+4+4+5+5 = 25
21은 불가능한 값이다. 그래프에서 가장 가벼운 간선 6개의 합이 이미 25이므로 신장 트리 비용은 25보다 작을 수 없다.
31은 크루스칼이 선택하지 않는 6 이상의 간선(B-C, C-E, D-G 등)이 포함된 신장 트리의 비용으로 최소가 아니다.
33도 7·8짜리 간선(B-D, E-F, D-F 등)이 섞인 경우의 비용으로 최소가 아니다.