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

Алгори́тм Бору́вки, алгоритм построения минимального остовного дерева во взвешенном связном неориентированном графе. Предложен в 1926 г. в работах чешского математика О. Борувки (^[1]; ^[2]).

Алгоритм является жадным. За ${\displaystyle E}$ и ${\displaystyle V}$ обозначаются множества рёбер и вершин графа ${\displaystyle G}$, за ${\displaystyle \vert E\vert }$ и ${\displaystyle \vert V\vert }$ – число рёбер и вершин в графе ${\displaystyle G}$ соответственно. Алгоритм использует (^[3] P. 3–36) процедуру сжатия по множеству нескольких вершин ${\displaystyle E^{\prime }\subseteq V}$ графа ${\displaystyle G}$, которая объединяет множество ${\displaystyle E^{\prime }}$ в одну новую вершину. Вес ребра от каждой вершины до новой определяется как вес ребра наименьшего веса между этой вершиной и вершиной из ${\displaystyle E^{\prime }}$ в старом графе ${\displaystyle G}$. При этом считается, что вес ребра между несвязанными ребром вершинами равен ${\displaystyle +\infty }$.

Пусть множество вершин ${\displaystyle E^{\prime }\subseteq V}$ таково, что подграф некоторого минимального остовного дерева графа ${\displaystyle G}$, порождённый ${\displaystyle E^{\prime }}$, связен. Пусть ${\displaystyle G^{\prime }}$ – результат сжатия графа ${\displaystyle G}$ по ${\displaystyle E^{\prime }}$. Тогда остовное дерево графа ${\displaystyle G}$ можно получить как порёберное объединение минимального остовного дерева графа ${\displaystyle G^{\prime }}$ и минимального остовного дерева, порождённого множеством ${\displaystyle E^{\prime }}$ подграфа ${\displaystyle G}$. Также данный факт остаётся верным и при сжатии нескольких непересекающихся множеств вершин.

Далее выполняются следующие шаги (^[4] P. 26):

1. Раскраска. Для каждой вершины раскрашиваем ребро между ней и ближайшей соседней вершиной. Рёбра, раскрашенные более одного раза, не отличаются от рёбер, раскрашенных единожды.
2. Сжатие. Сжимаем получившиеся компоненты связности на графе, порождённом раскрашенными рёбрами.
3. Рекурсивно повторяем предыдущие шаги, пока не найдём минимальное остовное дерево.

Объединение всех раскрашенных рёбер даёт искомое минимальное остовное дерево.

Раскраска и сжатие выполняются за линейное время ${\displaystyle O(\vert E\vert )}$. Так как при раскраске графа раскрашивается число рёбер, не меньшее половины числа его вершин, то алгоритм сделает ${\displaystyle O(\log \vert V\vert )}$ шагов прежде, чем найдёт минимальное остовное дерево. Таким образом, временна́я сложность алгоритма составляет ${\displaystyle O(\vert E\vert \log \vert V\vert )}$.

См. также «О большое».