크루스칼 알고리즘(Kruskal algorithm)은 에지를 가중치가 작은 것부터 큰 것 순으로 정렬합니다. 그 후에 E(T)에 에지를 하나씩 추가합니다. 사이클이 생기면 추가하지 않고 버립니다. 에지를 추가하다 트리가 되면 알고리즘을 중단합니다. 알고리즘 자체는 생각보다 간단합니다. 다만 사이클이 생긴 것을 어떻게 알 것인지가 관건입니다. 이 문제를 고민해 보겠습니다.