다음 그래프를 대상으로 Kruskal 알고리즘을 이용한 최소 비용 신장… | [계리직 컴퓨터일반] 14년 1회차 기출문제 상세 페이지

다섯 번째로 선택되는 간선의 비용은 12이다.
Kruskal 알고리즘은 간선을 비용 오름차순으로 보며 사이클을 만들지 않는 간선만 고른다. 3(V5–V6), 5(V2–V4), 6(V4–V5)을 차례로 고르고, 7(V4–V6)은 V4–V5–V6 사이클이 생겨 버린다. 이어 9(V3–V5)를 고른다.
10(V3–V4)과 11(V2–V3)은 이미 연결된 정점끼리라 사이클이 생겨 제외되고, V1을 잇는 12(V1–V3)가 다섯 번째로 선택되어 6개 정점의 신장 트리가 완성된다.
9: 네 번째로 선택된 간선의 비용이다.
10: V3와 V4가 이미 연결되어 있어 사이클이 생기므로 선택되지 않는다.
11: V2와 V3가 이미 연결되어 있어 사이클이 생기므로 선택되지 않는다.