다음 그래프에 크루스칼(Kruskal) 알고리즘을 적용하여 최소 신장 … | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지

크루스칼 알고리즘에서 마지막으로 포함되는 간선은 (c, d)이다.
가중치 순으로 (a, c) 1, (h, g) 1, (a, e) 2, (b, c) 2, (e, g) 2를 채택하면 a, b, c, e, g, h가 하나로 묶인다. 가중치 3에서는 (h, e)가 사이클을 만들어 버리고 (g, f)를 채택한다.
가중치 4·5의 (h, c), (a, b), (c, g)는 모두 사이클을 만들고, d를 처음 연결하는 (c, d) 5가 일곱 번째 간선으로 채택되어 신장 트리가 완성된다.
(a, b): a와 b가 이미 (a, c)·(b, c)로 연결되어 있어 사이클을 만들므로 제외된다.
(a, c): 가중치 1로 가장 먼저 채택되는 간선이다.
(b, c): 가중치 2로 초반에 채택되는 간선이다.