Алгоритм Борувки — это жадный алгоритм поиска минимального остовного дерева в графе или минимального остовного леса в случае несвязного графа.
Впервые он был опубликован в 1926 году Отакаром Боровкой как метод построения эффективной электросети для Моравии . [1] [2] [3] Алгоритм был заново открыт Шоке в 1938 году; [4] снова Флореком, Лукасевичем , Перкалем, Штейнхаусом и Зубжицким в 1951 году; [5] и снова Жоржем Соллином в 1965 году. [6] Этот алгоритм часто называют алгоритмом Соллина , особенно в литературе по параллельным вычислениям .
Алгоритм начинается с поиска ребра минимального веса, инцидентного каждой вершине графа, и добавления всех этих ребер в лес. Затем он повторяет аналогичный процесс поиска ребра с минимальным весом от каждого построенного дерева к другому дереву и добавляет все эти ребра в лес. Каждое повторение этого процесса уменьшает количество деревьев в каждом связном компоненте графа не более чем до половины этого прежнего значения, поэтому после логарифмического количества повторений процесс завершается. Когда это происходит, набор добавленных ребер образует минимальный остовный лес.
Следующий псевдокод иллюстрирует базовую реализацию алгоритма Борувки. В условных предложениях каждое ребро ув считается дешевле, чем «Нет». Цель заполненной переменной — определить, является ли лес 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 , если is-preferred-over( uv , wx ) , затем Установите uv как самое дешевое ребро для компонента u , пусть yz будет самым дешевым ребром для компонента v , если is-preferred- over( uv , yz ) then Set uv как самое дешевое ребро для компонента v , если для всех компонентов самое дешевое ребро установлено на «Нет», тогда // больше нельзя объединять деревья — мы закончили завершено := true else завершено : = false для каждого компонента, у которого самое дешевое ребро не «Нет». Добавить его самое дешевое ребро к E'функция is-preferred-over( Edge1 , Edge2 ) возвращается ( Edge2 имеет значение «Нет») или (вес( край1 ) < вес( край2 )) или (вес( ребро1 ) = вес( ребро2 ) и правило разрешения конфликтов ( ребро1 , ребро2 ))функция -правило разрешения конфликтов ( edge1 , Edge2 ) — правило разрешения конфликтов; возвращает true тогда и только тогда, когда край1 предпочтительнее края2 в случае ничьей.В качестве оптимизации можно удалить из G каждое ребро, соединяющее две вершины в одном и том же компоненте, чтобы это не тратило время на поиск самых дешевых ребер в более поздних компонентах.
Можно показать, что алгоритм Борувки выполняет O (log V ) итераций внешнего цикла до тех пор, пока он не завершится, и, следовательно, работает за время O ( E log V ) , где E — количество ребер, а V — количество вершин в G (при условии, что E ≥ V ). В плоских графах и, в более общем плане, в семействах графов, замкнутых с помощью второстепенных операций над графом, его можно заставить работать за линейное время, удаляя все ребра, кроме самого дешевого, между каждой парой компонентов после каждого этапа алгоритма. [7]
Другие алгоритмы решения этой задачи включают алгоритм Прима и алгоритм Краскала . Быстрые параллельные алгоритмы можно получить, объединив алгоритм Прима с алгоритмом Борувки. [8]
Более быстрый рандомизированный алгоритм минимального остовного дерева, частично основанный на алгоритме Борувки Каргера, Кляйна и Тарьяна, работает за ожидаемое время O( E ) . [9] Самый известный (детерминированный) алгоритм минимального остовного дерева Бернара Шазеля также частично основан на алгоритме Борувки и работает за время O( E α( E , V )) , где α — обратная функция Аккермана . [10] Эти рандомизированные и детерминированные алгоритмы сочетают в себе шаги алгоритма Борувки, уменьшающие количество компонентов, которые осталось соединить, с шагами другого типа, которые уменьшают количество ребер между парами компонентов.