Алгоритм Борувкаса - Википедия - Borůvkas algorithm

Анимация алгоритма Борувки
График и дерево
алгоритмы поиска
Списки
похожие темы

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

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

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

Псевдокод

Обозначая каждую вершину или набор связанных вершин "компонент ", псевдокод алгоритма Борувки:

алгоритм Борувка является    Вход: График грамм ребра которого имеют разные веса. выход: F минимальный остов грамм. Инициализировать лес F быть набором деревьев с одной вершиной, по одной для каждой вершины графа. пока F имеет более одного компонента делать        Найдите связанные компоненты F и пометьте каждую вершину грамм по его компоненту. Инициализировать самое дешевое ребро для каждого компонента на "Нет" для каждого край УФ из грамм делать            если ты и v иметь разные метки компонентов: если УФ дешевле самой дешевой кромки для компонента ты тогда                    Набор УФ как самый дешевый край для компонента ты                если УФ дешевле самой дешевой кромки для компонента v тогда                    Набор УФ как самый дешевый край для компонента v        для каждого компонент, самый дешевый край которого не "Нет" делать            Добавьте его самое дешевое преимущество в F

Если ребра не имеют различных весов, то можно использовать согласованное правило разрыва связей (например, разрыв связей по идентификаторам объектов ребер). Оптимизация (не требуется для анализа) заключается в удалении из грамм каждое ребро, которое соединяет две вершины в одном компоненте друг с другом.

Сложность

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

Пример

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

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

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

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

Примечания

  1. ^ Борувка, Отакар (1926). "O jistém problému minimálním" [О некой минимальной задаче]. Práce Mor. Přírodověd. Spol. В Брне III (на чешском и немецком языках). 3: 37–58.
  2. ^ Борувка, Отакар (1926). «Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Вклад в решение проблемы экономичного строительства электрических сетей)». Elektronický Obzor (на чешском языке). 15: 153–154.
  3. ^ Нешетржил, Ярослав; Милкова, Ева; Nešetřilová, Елена (2001). «Отакар Борувка о проблеме минимального остовного дерева: перевод обеих статей 1926 года, комментарии, история». Дискретная математика. 233 (1–3): 3–36. Дои: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". Математический коллоквиум (На французском). 2: 282–285. МИСТЕР  0048832.
  6. ^ Соллин, Жорж (1965). "Le tracé de canalisation". Программирование, игры и транспортные сети (На французском).
  7. ^ Эппштейн, Дэвид (1999). «Балки и гаечные ключи». В Sack, J.-R.; Уррутия, Дж. (ред.). Справочник по вычислительной геометрии. Эльзевир. С. 425–461.; Мареш, Мартин (2004). «Два алгоритма линейного времени для MST на второстепенных классах замкнутых графов» (PDF). Archivum Mathematicum. 40 (3): 315–320..
  8. ^ Бадер, Дэвид А .; Конг, Гоцзин (2006). «Быстрые алгоритмы с общей памятью для вычисления минимального остовного леса разреженных графов». Журнал параллельных и распределенных вычислений. 66 (11): 1366–1378. CiteSeerX  10.1.1.129.8991. Дои:10.1016 / j.jpdc.2006.06.001.
  9. ^ Каргер, Дэвид Р .; Klein, Philip N .; Тарьян, Роберт Э. (1995). «Рандомизированный алгоритм линейного времени для поиска минимальных остовных деревьев». Журнал ACM. 42 (2): 321–328. CiteSeerX  10.1.1.39.9012. Дои:10.1145/201019.201022.
  10. ^ Шазель, Бернар (2000). «Алгоритм минимального остовного дерева с обратной сложностью типа Аккермана» (PDF). J. ACM. 47 (6): 1028–1047. CiteSeerX  10.1.1.115.2318. Дои:10.1145/355541.355562.