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

Алгоритм Борувки — алгоритм поиска минимального остовного дерева (minimum spanning tree, MST) во взвешенном неориентированном связном графе. Впервые был опубликован в 1926 году Отакаром Борувкой.

Описание алгоритма

Пусть [math]T[/math] подграф графа [math]G[/math]. Изначально [math]T[/math] содержит все вершины из [math]G[/math] и не содержит ребер.

Будем добавлять в [math]T[/math] ребра следующим образом:

Пока [math]T[/math] не является деревом

1. Для каждой компоненты связности находим минимальное по весу ребро, которое связывает вершину из данной компоненты с вершиной, не принадлежащей данной компоненте.
2. Добавим в [math]T[/math] все ребра, которые хотя бы для одной компоненты связности оказались минимальными.

Получившийся граф [math]T[/math] является минимальным остовным деревом графа [math]G[/math].

Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес каждого ребра равен один. В [math]T[/math] могут быть добавлены все три ребра. Избежать эту проблему можно, выбирая в первом пункте среди ребер, равных по весу, ребро с наименьшим номером.

Доказательство будем проводить, считая веса всех ребер различными.

Доказательство корректности

Лемма:

Рассмотрим связный неориентированный взвешенный граф [math] G = (V, E) [/math] с инъективной весовой функцией [math]w : E \to \mathbb{R}[/math] . Тогда после первой итерации главного цикла алгоритма Борувки получившийся подграф можно достроить до MST.

Доказательство:

[math]\triangleright[/math]

Предположим обратное: пусть любое MST графа [math]G[/math] не содержит [math]T[/math]. Рассмотрим какое-нибудь MST. Тогда существует ребро [math]x[/math] из [math]T[/math] такое что [math]x[/math] не принадлежит MST. Добавив ребро [math]x[/math] в MST, получаем цикл в котором [math]x[/math] не максимально, т.к оно было минимальным. Тогда, исходя из критерия Тарьяна, получаем противоречие.

[math]\triangleleft[/math]

Теорема:

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

Доказательство:

[math]\triangleright[/math]

Очевидно, что алгоритм Борувки строит дерево.Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки текущий подграф [math]T[/math] можно достроить до MST. Докажем это по индукции. База: [math]n = 1[/math](Лемма). Переход: Пусть лес [math]T[/math], получившийся после [math]n[/math] итераций алгоритма, можно достроить до MST. Докажем, что после [math]n+1[/math] итерации получившийся лес [math]T'[/math] можно достроить до MST.Предположим обратное: [math]T'[/math] нельзя достроить до MST. Тогда существует [math]F[/math] = MST графа [math]G[/math], содержащее [math]T[/math] и не содержащее [math]T'[/math]. Тогда рассмотрим цикл, получающийся добавлением в [math]F[/math] какого-нибудь ребра [math]x[/math] из [math]T' - T[/math]. На этом цикле имеется ребро, большее по весу чем ребро [math]x[/math], иначе компонента для которой [math]x[/math] является минимальным ребром ни с кем больше ни связана.Исходя из критерия Тарьяна, получаем противоречие. Получаем [math]T'[/math] можно достроить до MST. Следовательно предположение индукции верно.

[math]\triangleleft[/math]

Реализация

У вершины есть поле comp — компонента связности, которой принадлежит эта вершина.

Graph Boruvka(Graph G) while T.size < n - 1 init() // для каждой компоненты вес минимального ребра равен бесконечности. findComp(T) // разбиваеv граф T на компоненты связности обычным dfs-ом for uv [math]\in[/math] E if u.comp != v.comp if minEdge[u.comp].w < uv.w minEdge[u.comp] = uv if minEdge[v.comp].w < uv.w minEdge[v.comp] = uv for k [math]\in[/math] Component // Component — множество компонент связности в T T.addEdge(minEdge[k]) // добавляем ребро если его не было в T return T;

Асимптотика

Время работы внутри главного цикла будет равно [math]O(E + V)[/math].

Количество итераций, которое выполняется главным циклом равно [math]O(\log{V})[/math] так как на каждой итерации количество компонент связности уменьшается в 2 раза (изначально количество компонент равно [math]|V|[/math], в итоге должна стать одна компонента).

Общее время работы алгоритма получается [math]O(E\log{V})[/math].

Ссылки

• Minimum Spanning Trees
• Алгоритм Борувки— Википедия

См. также

• Алгоритм Прима
• Алгоритм Краскала