각 간선 의 가중치를 로 두고 최소 스패닝 트리 를 구한다. 최소 비용은
이다.
트리에 속하지 않는 간선들을 먼저 모두 제거하고, 트리 간선들을 나중에 제거하는 순서를 출력한다. 각 부분 안에서는 임의의 순서로 제거해도 된다.
최소 스패닝 트리를 구할 때 크루스칼 알고리즘을 이용할 경우, 시간 복잡도는 , 공간 복잡도는 이다.
증명
간선 제거로 컴포넌트 수가 늘어나는 연산은 정확히 번이다. 제거 과정을 거꾸로 보면, 이 간선들은 서로 다른 컴포넌트를 연결하며 전체 정점을 잇는다. 따라서 이 간선들의 집합은 스패닝 트리이다.
모든 간선에 기본 비용 를 지불한다고 생각하자. 위 트리의 간선은 비용이 이므로 를 추가로 지불한다. 기본 비용은 고정되어 있으므로, 추가 비용을 최소화하는 최소 스패닝 트리가 하한을 준다.
제시한 제거 순서의 전반에는 트리가 남아 있어 연결이 끊어지지 않는다. 후반에는 남은 그래프가 포레스트이므로 간선을 지울 때마다 연결이 끊어진다. 따라서 위 하한을 실제로 달성한다.
