다음 가중 그래프(weighted graph)는 9개의 정점과 1부터 … | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 16년 1회차
다음 가중 그래프(weighted graph)는 9개의 정점과 1부터 19까지의 가중치(비용)를 갖는 19개의 간선으로 구성되어 있다. Kruskal 알고리즘을 사용하여 최소 비용 신장 트리(minimum cost spanning tree)를 구성할 때, 최소 비용과 마지막으로 선택되는 간선을 순서대로 나열한 것은?
1
43, (G, E)
2
43, (B, F)
3
44, (G, E)
4
44, (B, F)
해설
Kruskal 알고리즘의 최소 비용은 44이고, 마지막으로 선택되는 간선은 (B, F)이다.
가중치가 작은 간선부터 사이클이 생기지 않으면 채택한다. 1(H, C), 2(I, G), 3(G, H)를 채택하고 4(I, H)는 사이클이 생겨 버린다. 이어서 5(H, E), 6(A, C), 7(A, B), 8(B, D)를 채택한다.
9(E, C), 10(D, A), 11(G, E)는 모두 사이클을 만들어 버리고, 12(F, B)를 채택하면 정점 9개에 간선 8개가 되어 종료한다.
- 최소 비용 43: 채택된 8개 간선 가중치의 합은 44이다.
- 마지막 간선 (G, E): G와 E는 이미 H를 통해 연결되어 있어 가중치 11인 이 간선은 사이클을 만들므로 채택되지 않는다.
오류나 개정된 내용이 보이면 알려주세요
