가중치 무방향 그래프에서 크루스칼(Kruskal) 알고리즘을 이용해 최… | [7급 서울시 자료구조론] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 자료구조론] 26년 1회차
가중치 무방향 그래프에서 크루스칼(Kruskal) 알고리즘을 이용해 최소 비용 신장 트리를 구성하려고 한다. 간선의 가중치는 <보기>와 같다. 크루스칼 알고리즘으로 간선을 선택하는 과정에서, 세 번째로 신장 트리에 포함되는 간선은?(A, B): 2, (A, C): 3, (B, C): 1, (B, D): 5, (C, D): 4
1
(A, B)
2
(A, C)
3
(B, D)
4
(C, D)
해설
세 번째로 신장 트리에 포함되는 간선은 (C, D)이다.
크루스칼 알고리즘은 가중치가 작은 간선부터 고르되 사이클을 만드는 간선은 제외한다.
(B, C) 1 선택 → (A, B) 2 선택 → (A, C) 3은 A-B-C 사이클을 만들어 제외 → (C, D) 4 선택.
- (A, B): 두 번째로 포함되는 간선이다.
- (A, C): 사이클을 만들어 제외된다.
- (B, D): 정점 4개의 신장 트리는 간선 3개로 이미 완성되어 선택되지 않는다.
오류나 개정된 내용이 보이면 알려주세요