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

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

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

1. Построим граф [math]T[/math]. Изначально [math]T[/math] содержит все вершины из [math]G[/math] и не содержит ребер (каждая вершина в графе [math]T[/math] — отдельная компонента связности).
2. Будем добавлять в [math]T[/math] ребра следующим образом, пока [math]T[/math] не является деревом
   • Для каждой компоненты связности находим минимальное по весу ребро, которое связывает эту компоненту с другой.
   • Добавим в [math]T[/math] все найденные рёбра.
3. Получившийся граф [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 — компонента связности, которой принадлежит эта вершина.

// [math]G[/math] — исходный граф // [math]w[/math] — весовая функция function [math]\mathtt{boruvkaMST}():[/math] while [math]T\mathtt{.size} \lt n - 1[/math] for [math]k \in [/math] Component // Component — множество компонент связности в [math]T[/math] [math]w(\mathtt{minEdge}[k])=\infty[/math] // для каждой компоненты связности вес минимального ребра = [math]\infty[/math] [math]\mathtt{findComp(}T\mathtt{)}[/math] // разбиваем граф [math]T[/math] на компоненты связности обычным dfs-ом for [math]\mathtt{(u,v)} \in E [/math] if [math]\mathtt{u.comp} \neq \mathtt{v.comp}[/math] if [math]w(\mathtt{minEdge}[\mathtt{u.comp}]) \lt w(u,v)[/math] [math]\mathtt{minEdge}[\mathtt{u.comp}] = (u,v)[/math] if [math]w(\mathtt{minEdge}[\mathtt{v.comp}]) \lt w(u,v)[/math] [math]\mathtt{minEdge}[\mathtt{v.comp}] = (u,v)[/math] for [math]k \in [/math] Component [math]T\mathtt{.addEdge}(\mathtt{minEdge}[k])[/math] // добавляем ребро если его не было в [math]T[/math] return [math]T[/math]

Пример

Изображение	Компоненты связности	Описание
		Начальный граф [math]T[/math]
	a b c d e	Распределим вершины по компонентам.
	a b c d e	Пометим минимальные пути между компонентами.
	bae cd	Объединим соединившиеся компоненты в одну и добавим минимальные рёбра к графу [math]T[/math]
	bae cd	Пометим минимальные пути между компонентами.
	baecd	Объединим соединившиеся компоненты в одну и добавим минимальные рёбра к графу [math]T[/math]

Асимптотика

Внешний цикл повторяется [math]\log{V}[/math] раз, так как количество компонент связности каждый раз уменьшается в двое и изначально равно количеству вершин. Что же касается внутреннего цикла, то он выполняется за [math]E[/math], где [math]E[/math] — количество рёбер в исходном графе. Следовательно конечное время работы алгоритма [math]O(E\log{V})[/math].

См. также

• Алгоритм Прима
• Алгоритм Краскала
• Алгоритм двух китайцев

Источники информации

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