다음 그래프에 대해 크루스칼(Kruskal) 알고리즘에 의한 최소 신장… | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 23년 1회차
다음 그래프에 대해 크루스칼(Kruskal) 알고리즘에 의한 최소 신장 트리(MST, Minimum Spanning Tree)를 계산할 때, 5번째로 MST에 포함되는 간선은? (단, 초기의 MST는 ∅이다)
1
(b, c)
2
(b, g)
3
(c, e)
4
(d, e)
해설
크루스칼 알고리즘에서 다섯 번째로 MST에 포함되는 간선은 (c, e)이다.
가중치 오름차순으로 (a, b) 2, (c, f) 3, (g, f) 4, (b, g) 5가 사이클 없이 채택되어 a, b, g, f, c가 한 집합이 된다.
가중치 6인 (b, c)는 같은 집합의 두 노드를 이어 사이클을 만들므로 버리고, 같은 가중치의 (c, e)가 다섯 번째로 채택된다.
- (b, c): 가중치는 같지만 사이클을 만들어 제외된다.
- (b, g): 네 번째로 채택된 간선이다.
- (d, e): 가중치 8로 (c, e) 다음, 여섯 번째로 채택된다.
오류나 개정된 내용이 보이면 알려주세요