다음과 같이 인접 행렬로 표현된 가중 그래프(weighted graph… | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 17년 1회차
다음과 같이 인접 행렬로 표현된 가중 그래프(weighted graph)에 대하여 최소 비용 신장 트리(minimum cost spanning tree)를 구성했을 때, 최소 비용은?
| [0] | [1] | [2] | [3] | |
|---|---|---|---|---|
| [0] | 0 | 5 | 1 | 2 |
| [1] | 5 | 0 | ∞ | 4 |
| [2] | 1 | ∞ | 0 | 3 |
| [3] | 2 | 4 | 3 | 0 |
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이다.
오류나 개정된 내용이 보이면 알려주세요