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