다음 그래프를 이용하여 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인 간선 두 개를 채택하면 모든 정점이 연결된다.

1+2+2+4+4=131 + 2 + 2 + 4 + 4 = 13

  • 11: 합을 13보다 줄이려면 가중치 3 간선을 넣어야 하는데, 이 간선은 사이클을 만들므로 신장 트리에 쓸 수 없다.
  • 12: 가중치 4 간선 하나를 가중치 3 간선으로 바꾼 값이지만, 가중치 3 간선은 사이클을 만들어 채택되지 않는다.
  • 14: 가중치 5 이상 간선은 필요 없이 이미 모든 정점이 연결되므로 비용이 더 커지지 않는다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 12년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기