Введение
Метод поиска минимальных остовных деревьев
Алгоритм Борувки — это жадный алгоритм для поиска минимального остовного дерева в графе или минимального остовного леса в случае несвязного графа. Он был впервые опубликован в 1926 году Отакаром Борувкой как метод построения эффективной электрической сети для Моравии. Алгоритм был повторно открыт Шоке в 1938 году, затем Флореком, Лукасевичем, Перкалем, Штейнхаусом и Зубржицким в 1951 году, и снова Жоржем Соллином в 1965 году. Этот алгоритм часто называют алгоритмом Соллина, особенно в литературе по параллельным вычислениям. Алгоритм начинается с поиска ребра минимального веса, инцидентного каждой вершине графа, и добавления всех этих рёбер в лес. Затем он повторяет аналогичный процесс, находя ребро минимального веса из каждого построенного дерева в другое дерево, и добавляет все эти рёбра в лес. Каждое повторение этого процесса уменьшает количество деревьев в каждой связной компоненте графа как минимум вдвое, поэтому после логарифмически большого числа повторений процесс завершается. Когда это происходит, набор добавленных рёбер образует минимальный остовный лес.
or a minimum spanning forest in the case of a graph that is not connected. It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia. The algorithm was rediscovered by Choquet in 1938; again by Florek, Łukasiewicz, Perkal, Steinhaus, and Zubrzycki in 1951; and again by Georges Sollin in 1965. This algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature. The algorithm begins by finding the minimum weight edge incident to each vertex of the graph, and adding all of those edges to the forest. Then, it repeats a similar process of finding the minimum weight edge from each tree constructed so far to a different tree, and adding all of those edges to the forest. Each repetition of this process reduces the number of trees, within each connected component of the graph, to at most half of this former value,
so after logarithmically many repetitions the process finishes. When it does, the set of edges it has added forms the minimum spanning forest.
Сложность
Алгоритм Боровки можно показать, что выполняет итераций внешней петли до завершения, и, следовательно, работает за время, где E — количество ребер, а V — количество вершин в G (при условии, что E ≥ V). В планарных графах и, в более общем случае, в семействах графов, замкнутых относительно минорных операций над графами, его можно заставить работать за линейное время, удаляя все, кроме самого дешевого ребра между каждой парой компонент после каждой стадии алгоритма.
Пример
Компоненты изображения Описание. Это наш исходный взвешенный граф. Числа рядом с ребрами указывают их вес. Изначально каждая вершина сама по себе является компонентой (голубые круги). {A,B,D,F} {C,E,G} В первой итерации внешнего цикла добавляется ребро минимального веса, исходящее из каждой компоненты. Некоторые ребра выбираются дважды (AD, CE). Осталось две компоненты. {A,B,C,D,E,F,G} Во второй и заключительной итерации добавляется ребро минимального веса, исходящее из каждой из двух оставшихся компонент. В данном случае это оказывается одно и то же ребро. Осталась одна компонента, и мы закончили. Ребро BD не рассматривается, так как обе его конечные точки находятся в одной и той же компоненте.
Другие алгоритмы
Другие алгоритмы для решения этой задачи включают алгоритм Прима и алгоритм Крускала. Быстрые параллельные алгоритмы можно получить, комбинируя алгоритм Прима с алгоритмом Борувки. Более быстрый рандомизированный алгоритм поиска минимального остовного дерева, частично основанный на алгоритме Борувки, разработанный Каргером, Клейном и Таряном, работает в среднем за время O(E). Наилучший известный (детерминированный) алгоритм поиска минимального остовного дерева, разработанный Бернардом Шазелем, также частично основан на алгоритме Борувки и работает за время O(E α(E,V)), где α — обратная функция Аккермана. Эти рандомизированные и детерминированные алгоритмы сочетают шаги алгоритма Борувки, уменьшающие число компонент, которые необходимо соединить, с шагами другого типа, уменьшающими число ребер между парами компонент.