다음 그래프의 최소 비용 신장 트리(minimum cost spanni… | [7급 국가직 자료구조론] 26년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 26년 1회차
다음 그래프의 최소 비용 신장 트리(minimum cost spanning tree)에 대한 설명으로 옳은 것은?
1
사이클이 있어 최소 비용 신장 트리가 존재하지 않는다.
2
가중치가 가장 큰 간선은 최소 비용 신장 트리에 포함되지 않는다.
3
모든 간선 가중치가 서로 달라 최소 비용 신장 트리의 개수는 1이다.
4
두 정점 B와 D 사이의 최단 경로는 최소 비용 신장 트리에 포함된다.
해설
간선 가중치가 모두 달라 최소 비용 신장 트리는 유일하므로 개수가 1이라는 설명이 옳다.
간선은 E–F 1, C–D 2, A–B 3, A–C 4, B–D 5, B–C 6, D–E 7이다. 크루스칼 알고리즘으로 가중치 순서대로 고르면 E–F, C–D, A–B, A–C를 채택하고, B–D와 B–C는 사이클을 만들어 버리며, D–E를 채택해 총비용 17의 트리가 된다.
- 사이클이 있어도 연결 그래프이면 신장 트리는 항상 존재하므로 존재하지 않는다는 설명은 틀리다.
- 가중치가 가장 큰 D–E 간선은 E, F를 나머지와 잇는 유일한 간선(브리지)이라 반드시 포함된다.
- B와 D 사이의 최단 경로는 직접 간선 B–D(비용 5)인데, 이 간선은 트리에 포함되지 않는다(트리 경로 B–A–C–D는 비용 9).
오류나 개정된 내용이 보이면 알려주세요