다음 그래프를 이용하여 Kruskal 알고리즘을 적용하였을 때, 생성된… | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 12년 1회차
다음 그래프를 이용하여 Kruskal 알고리즘을 적용하였을 때, 생성된 최소 비용 신장 트리의 비용은?
1
11
2
12
3
13
4
14
해설
Kruskal 알고리즘으로 만든 최소 비용 신장 트리의 비용은 13이다.
정점 6개이므로 간선 5개가 필요하다. 가중치가 작은 간선부터 사이클이 생기지 않는 것만 고르면 1 → 2 → 2를 채택하고, 가중치 3인 간선은 이미 연결된 두 정점을 잇는 사이클이 되어 버린다. 이어서 가중치 4인 간선 두 개를 채택하면 모든 정점이 연결된다.
- 11: 합을 13보다 줄이려면 가중치 3 간선을 넣어야 하는데, 이 간선은 사이클을 만들므로 신장 트리에 쓸 수 없다.
- 12: 가중치 4 간선 하나를 가중치 3 간선으로 바꾼 값이지만, 가중치 3 간선은 사이클을 만들어 채택되지 않는다.
- 14: 가중치 5 이상 간선은 필요 없이 이미 모든 정점이 연결되므로 비용이 더 커지지 않는다.
오류나 개정된 내용이 보이면 알려주세요
