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

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

Анимация алгоритма Борувки
Сорт	Алгоритм минимального остовного дерева
Структура данных	График
Худший вариант производительности	${\displaystyle O(|E|\log |V|)}$

Алгоритм Борувки — это жадный алгоритм для поиска минимального остовного дерева в графе или минимального остовного леса в случае несвязного графа.

Впервые он был опубликован в 1926 году Отакаром Борувкой как метод построения эффективной электросети для Моравии . ^{[1] [2] [3]} Алгоритм был заново открыт Шоке в 1938 году; ^[4] снова Флореком, Лукасевичем , Перкалем, Штейнхаусом и Зубжицким в 1951 году; ^[5] и снова Жоржем Соллином в 1965 году. ^[6] Этот алгоритм часто называют алгоритмом Соллина , особенно в литературе по параллельным вычислениям .

Алгоритм начинается с поиска ребра минимального веса, инцидентного каждой вершине графа, и добавления всех этих ребер в лес. Затем он повторяет аналогичный процесс поиска ребра минимального веса из каждого дерева, построенного до сих пор, в другое дерево и добавления всех этих ребер в лес. Каждое повторение этого процесса уменьшает количество деревьев в каждом связанном компоненте графа максимум до половины этого прежнего значения, поэтому после логарифмически большого количества повторений процесс завершается. Когда это происходит, набор добавленных им ребер образует минимальный остовный лес.

Следующий псевдокод иллюстрирует базовую реализацию алгоритма Борувки. В условных предложениях каждое ребро uv считается более дешевым, чем "None". Целью завершенной переменной является определение того, является ли лес F все еще остовным лесом.

Если ребра не имеют различных весов, то необходимо использовать последовательное правило разрешения конфликтов , например, основанное на некотором общем порядке вершин или ребер. Этого можно добиться, представив вершины в виде целых чисел и сравнив их напрямую; сравнив их адреса памяти и т. д. Правило разрешения конфликтов необходимо для того, чтобы гарантировать, что созданный граф действительно является лесом, то есть не содержит циклов. Например, рассмотрим треугольный граф с узлами { a , b , c } и всеми ребрами веса 1. Тогда цикл может быть создан, если мы выберем ab в качестве ребра с минимальным весом для { a }, bc для { b } и ca для { c }. Правило разрешения конфликтов, которое упорядочивает ребра сначала по источнику, а затем по назначению, предотвратит создание цикла, что приведет к минимальному остовному дереву { ab , bc }.

Алгоритм Борувка имеет  входные данные: взвешенный неориентированный граф G = ( V , E ). Выходные данные:  F , минимальный остовной лес графа G . Инициализируем лес F как ( V , E ′ ), где E ′ = {}. завершено :  = false  пока не завершено  do Найдите связные компоненты F и назначьте каждой вершине ее компонент Инициализируйте самое дешевое ребро для каждого компонента как «Нет» для каждого ребра uv в E , где u и v находятся в разных компонентах F : пусть wx будет самым дешевым ребром для компонента u  if is-preferred-over( uv , wx ) then Установить uv как самое дешевое ребро для компонента u let yz будет самым дешевым ребром для компонента v  if is-preferred-over( uv , yz ) then Установить uv как самое дешевое ребро для компонента v  if all components has cheap edge set to "None" then  // больше деревьев нельзя объединить — мы закончили done  :  = true  else  complete  := false  для каждого компонента, самое дешевое ребро которого не равно "None" do Добавить его самое дешевое ребро к E'функция is-preferred-over( edge1 , edge2 ) возвращает ( edge2 is "None") или (вес( ребро1 ) < вес( ребро2 )) или (вес( ребро1 ) = вес( ребро2 ) и правило-разрешения-ничьи( ребро1 , ребро2 ))function tie-breaking-rule( edge1 , edge2 ) — это правило разрешения конфликтов; возвращает значение true тогда и только тогда, когда в случае конфликта конфликтующих сторон конфликтующее положение конфликтующих сторон предпочтительнее конфликта конфликтующих сторон .

В качестве оптимизации можно удалить из G каждое ребро, соединяющее две вершины в одном компоненте, чтобы оно не увеличивало время поиска самых дешевых ребер в последующих компонентах.

Можно показать, что алгоритм Борувки требует O (log V ) итераций внешнего цикла до тех пор, пока он не завершится, и, следовательно, выполняется за время O ( E log V ) , где E — число ребер, а V — число вершин в G (предполагая, что E ≥ V ). В планарных графах и, в более общем смысле, в семействах графов, замкнутых относительно второстепенных операций графа, его можно заставить работать за линейное время, удаляя все, кроме самого дешевого ребра между каждой парой компонентов после каждого этапа алгоритма. ^[7]

Изображение	компоненты	Описание
	{А} { Б } {В} {Г} {Д} {Е} {Ж}	Это наш исходный взвешенный граф. Числа около ребер указывают их вес. Изначально каждая вершина сама по себе является компонентом (синие кружки).
	{А,Б,Г,Е} {С,Д,Ж}	В первой итерации внешнего цикла добавляется минимальное ребро веса из каждого компонента. Некоторые ребра выбираются дважды (AD, CE). Остается два компонента.
	{А,Б,В,Г,Д,Е,Ж}	Во второй и последней итерации добавляется минимальное ребро веса из каждого из двух оставшихся компонентов. Это одно и то же ребро. Остается один компонент, и мы закончили. Ребро BD не рассматривается, поскольку обе конечные точки находятся в одном компоненте.

Другие алгоритмы для этой задачи включают алгоритм Прима и алгоритм Крускала . Быстрые параллельные алгоритмы могут быть получены путем объединения алгоритма Прима с алгоритмом Борувки. ^[8]

Более быстрый рандомизированный алгоритм минимального остовного дерева, частично основанный на алгоритме Борувки, разработанный Каргером, Клейном и Тарьяном, работает за ожидаемое время O( E ) . ^[9] Самый известный (детерминированный) алгоритм минимального остовного дерева Бернара Шазелла также частично основан на алгоритме Борувки и работает за время O( E α( E , V )) , где α — обратная функция Аккермана . ^[10] Эти рандомизированные и детерминированные алгоритмы объединяют шаги алгоритма Борувки, уменьшая количество компонентов, которые остаются для соединения, с шагами другого типа, которые уменьшают количество ребер между парами компонентов.