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

редактировать
Анимация алгоритма Борувки

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

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

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

СОДЕРЖАНИЕ

  • 1 Псевдокод
  • 2 Сложность
  • 3 Пример
  • 4 Другие алгоритмы
  • 5 Примечания

Псевдокод

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

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

algorithm Borůvka is input: A weighted undirected graph G = (V, E). output: F, a minimum spanning forest of G. Initialize a forest F to (V, E') where E' = {}. completed := false while not completed do Find the connected components  of F and assign to each vertex its component Initialize the cheapest edge for each component to "None" for each edge uv in E, where u and v are in different components of F: let wx be the cheapest edge for the component of u if is-preferred-over(uv, wx) then Set uv as the cheapest edge for the component of u let yz be the cheapest edge for the component of v if is-preferred-over(uv, yz) then Set uv as the cheapest edge for the component of v if all components have cheapest edge set to "None" then // no more trees can be merged -- we are finished completed := true else completed := false for each component whose cheapest edge is not "None" do Add its cheapest edge to E' function is-preferred-over(edge1, edge2) is return (edge1 is "None") or (weight(edge1) lt; weight(edge2)) or (weight(edge1) = weight(edge2) and tie-breaking-rule(edge1, edge2)) function tie-breaking-rule(edge1, edge2) is The tie-breaking rule; returns true if and only if edge1 is preferred over edge2 in the case of a tie.

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

Сложность

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

Пример

Изображение составные части Описание
Алгоритм Борувки 1.svg {A} {B} {C} {D} {E} {F} {G} Это наш исходный взвешенный график. Цифры у краев обозначают их вес. Изначально каждая вершина сама по себе является компонентом (синие кружки).
Алгоритм Борувки 2.svg {A, B, D, F} {C, E, G} В первой итерации внешнего цикла добавляется край минимального веса для каждого компонента. Некоторые ребра выделяются дважды (AD, CE). Остались две составляющие.
Алгоритм Борувки 3.svg {A, B, C, D, E, F, G} Во второй и последней итерации добавляется край минимального веса каждого из двух оставшихся компонентов. Это одна и та же кромка. Остается один компонент, и все готово. Край BD не рассматривается, потому что обе конечные точки находятся в одном компоненте.

Другие алгоритмы

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

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

Заметки

  1. ^ Борувка, Отакар (1926). "O jistém problému minimálním" [О некоторой минимальной задаче]. Práce Mor. Přírodověd. Spol. V Brně III (на чешском и немецком языках). 3: 37–58.
  2. ^ Борувка, Отакар (1926). «Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí». Электронный обзор (на чешском языке). 15: 153–154.
  3. ^ Нешетржил, Ярослав ; Милкова, Ева; Nešetřilová, Елена (2001). «Отакар Борувка о проблеме минимального остовного дерева: перевод обеих статей 1926 года, комментарии, история». Дискретная математика. 233 (1–3): 3–36. DOI : 10.1016 / S0012-365X (00) 00224-7. hdl : 10338.dmlcz / 500413. Руководство по ремонту   1825599.
  4. ^ Шоке, Гюстав (1938). "Этюд определенных маршрутов". Comptes Rendus de l'Académie des Sciences (на французском языке). 206: 310–313.
  5. ^ Флорек, К.; Лукашевич, Дж. ; Perkal, J.; Штайнхаус, Гюго ; Зубжицкий, С. (1951). "Sur la liaison et la Division des points d'un ensemble fini". Colloquium Mathematicae (на французском языке). 2: 282–285. Руководство по ремонту   0048832.
  6. ^ Sollin, Жорж (1965). "Le tracé de canalisation". Программирование, игры и транспортные сети (на французском языке).
  7. ^ Эпштайна, Дэвид (1999). «Острова и гаечные ключи». В мешке, Ж.-Р. ; Уррутия, Дж. (Ред.). Справочник по вычислительной геометрии. Эльзевир. С. 425–461.; Мареш, Мартин (2004). «Два алгоритма линейного времени для MST на второстепенных классах замкнутых графов» (PDF). Archivum Mathematicum. 40 (3): 315–320..
  8. ^ Бадер, Дэвид А.; Конг, Гоцзин (2006). «Быстрые алгоритмы с общей памятью для вычисления минимального остовного леса разреженных графов». Журнал параллельных и распределенных вычислений. 66 (11): 1366–1378. CiteSeerX   10.1.1.129.8991. DOI : 10.1016 / j.jpdc.2006.06.001.
  9. ^ Каргер, Дэвид Р.; Klein, Philip N.; Тарьян, Роберт Э. (1995). «Рандомизированный алгоритм линейного времени для поиска минимальных остовных деревьев». Журнал ACM. 42 (2): 321–328. CiteSeerX   10.1.1.39.9012. DOI : 10.1145 / 201019.201022.
  10. ^ Chazelle, Bernard (2000). «Минимальный алгоритм остовного дерева с обратной сложностью типа Аккермана» (PDF). J. ACM. 47 (6): 1028–1047. CiteSeerX   10.1.1.115.2318. DOI : 10.1145 / 355541.355562.
Последняя правка сделана 2024-01-11 03:58:37
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте