Переформулируем лемму о безопасном ребре в частном случае:
Лемма. Для любой вершины минимальное инцидентное ей реборо является безопасным.
Доказательство. Пусть есть минимальный остов, в котором для какой-то вершины $v$ нет её минимального инцидентного ребра. Тогда, если добавить это ребро, образуется цикл, из которого можно удалить другое ребро, тоже инцидентное $v$, но имеющее не меньший вес.
Алгоритм Борувки опирается на этот факт и заключается в следующем:
- Для каждой вершины найдем минимальное инцидентное ей ребро.
- Добавим все такие рёбра в остов (это безопасно — см. лемму) и сожмем получившиеся компоненты, то есть объединим списки смежности вершин, которые эти рёбра соединяют.
- Повторяем шаги 1-2, пока в графе не останется только одна вершина-компонента.
Алгоритм может работать неправильно, если в графе есть ребра, равные по весу. Пример: «треугольник» с одинаковыми весами рёбер. Избежать такую ситуацию можно, введя какой-то дополнительный порядок на рёбрах — например, сравнивая пары из веса и номера ребра.
#Асимптотика
Заметим, что на каждой итерации каждая оставшаяся вершина будет задействована в «мердже». Это значит, что количество вершин-компонент уменьшится хотя бы вдвое, а значит всего итераций будет не более $O(\log n)$.
На каждой итерации мы просматриваем почти все рёбра, так что итоговое время работы составит $O(m \log n)$.
#Зачем это нужно?
Алгоритм неприятно реализовывать. Настолько неприятно, что автор это делать не будет. Однако, алгоритм очень полезен на практике, потому что в «реальных» графах он работает за линейное время.
Утверждение. В случае планарных графов алгоритм работает за $O(n)$.
Доказательство. Из формулы Эйлера нам известно, что рёбер в планарном графе $O(n)$. Так как подграф планарного графа тоже всегда планарен, то после каждой итерации размер нашей задачи уменьшается в честные 2 раза — меньше становится не только вершин, но и рёбер тоже. Значит, алгоритм будет работать за $O(n) + O(\frac{n}{2}) + O(\frac{n}{4}) + \ldots = O(n)$.
Также, в отличие от алгоритмов Прима и Крускала, его можно легко распараллелить. «Параллельная сложность» у него $O(\log^2 v)$: нужно каждую итерацию просто искать минимум по оставшимся рёбрам и мерджить списки смежности, что в свою очередь хоть и очень нетривиально, но можно сделать за $O(\log v)$.