Алгоритм Борувки - Алгоритмика

Переформулируем лемму о безопасном ребре в частном случае:

Лемма. Для любой вершины минимальное инцидентное ей реборо является безопасным.

Доказательство. Пусть есть минимальный остов, в котором для какой-то вершины $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)$ .