다음과 같이 인접 행렬로 표현된 가중 그래프(weighted graph… | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 17년 1회차
다음과 같이 인접 행렬로 표현된 가중 그래프(weighted graph)에 대하여 최소 비용 신장 트리(minimum cost spanning tree)를 구성했을 때, 최소 비용은?
[0][1][2][3]
[0]0512
[1]50∞4
[2]1∞03
[3]2430
1
6
2
7
3
8
4
9
해설

최소 비용 신장 트리의 비용은 7이다.

간선을 가중치 순으로 나열하면 (0,2)=1, (0,3)=2, (2,3)=3, (1,3)=4, (0,1)=5이고, 정점 1과 2 사이는 ∞이므로 간선이 없다. 크루스칼 알고리즘으로 사이클이 생기지 않는 간선만 고른다.

  • (0,2)=1과 (0,3)=2를 차례로 선택한다.
  • (2,3)=3은 정점 0을 거쳐 이미 연결되어 사이클이 생기므로 제외한다.
  • (1,3)=4를 선택하면 정점 4개를 간선 3개로 모두 잇게 되어 완성된다.

합계는 1+2+4=7이다.

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

이어서 풀어보기

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