안전한 간선에 대한 보조정리를 특수한 경우에 맞게 다시 정식화합시다:
보조정리. 임의의 정점에 대해, 그 정점에 인접한 간선 중 가중치가 최소인 간선은 안전합니다.
증명. 어떤 정점 $v$에 대해 그 정점의 최소 인접 간선을 포함하지 않는 최소 신장 트리가 있다고 합시다. 그러면 이 간선을 추가할 때 사이클이 생기며, 이 사이클에서 마찬가지로 $v$에 인접하지만 가중치가 더 작지 않은 다른 간선을 제거할 수 있습니다.
보루프카 알고리즘은 이 사실에 기반하며, 다음과 같이 진행됩니다:
- 각 정점에 대해 그 정점에 인접한 최소 간선을 찾습니다.
- 이러한 간선을 모두 신장 트리에 추가하고(이는 안전합니다 — 보조정리를 참고하십시오), 그 결과로 생긴 컴포넌트를 압축합니다. 즉, 이 간선들이 연결하는 정점들의 인접 리스트를 합칩니다.
- 그래프에 컴포넌트 정점이 하나만 남을 때까지 1~2단계를 반복합니다.
그래프에 가중치가 같은 간선이 있으면 알고리즘이 올바르게 동작하지 않을 수 있습니다. 예: 간선 가중치가 모두 같은 «삼각형»입니다. 간선에 어떤 추가적인 순서를 도입하면 이러한 상황을 피할 수 있습니다. 예를 들어 가중치와 간선 번호의 쌍을 비교하는 방법이 있습니다.
#점근적 복잡도
각 반복마다 남아 있는 모든 정점이 «병합»에 참여한다는 점에 주목합시다. 이는 정점-컴포넌트의 개수가 적어도 절반으로 줄어든다는 것을 의미하며, 따라서 전체 반복 횟수는 $O(\log n)$ 이하입니다.
각 반복마다 거의 모든 간선을 살펴보므로, 최종 실행 시간은 $O(m \log n)$이 됩니다.
#이것이 왜 필요합니까?
이 알고리즘은 구현하기가 까다롭습니다. 얼마나 까다로운지 저자는 구현하지 않겠습니다. 그러나 이 알고리즘은 실제로 매우 유용한데, «실제» 그래프에서는 선형 시간에 동작하기 때문입니다.
명제. 평면 그래프의 경우 이 알고리즘은 $O(n)$ 시간에 동작합니다.
증명. 오일러 공식에 의해 평면 그래프의 간선 수는 $O(n)$임을 알고 있습니다. 평면 그래프의 부분 그래프 역시 항상 평면 그래프이므로, 매 반복이 끝날 때마다 문제의 크기는 정확히 절반으로 줄어듭니다. 정점뿐 아니라 간선도 함께 줄어들기 때문입니다. 따라서 알고리즘은 $O(n) + O(\frac{n}{2}) + O(\frac{n}{4}) + \ldots = O(n)$의 시간에 동작합니다.
또한 프림 알고리즘이나 크루스칼 알고리즘과 달리, 이 알고리즘은 쉽게 병렬화할 수 있습니다. 이 알고리즘의 「병렬 복잡도」는 $O(\log^2 v)$입니다. 각 반복마다 남은 간선들 중에서 최솟값을 찾고 인접 리스트를 병합하기만 하면 되는데, 이 병합은 매우 까다롭기는 하지만 $O(\log v)$에 수행할 수 있습니다.