Алгоритм Борувки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
Строка 10: Строка 10:
  
  
Будем последовательно строить подграф <tex>F</tex> графа <tex>G</tex> ("растущий лес"), поддерживая следующий инвариант: на каждом шаге <tex>F</tex> можно достроить до некоторого MST. Начнем с того, что включим в <tex>F</tex> все вершины графа <tex>G</tex>. Теперь будем обходить множество <tex>EG</tex> в порядке увеличения веса ребер. Добавление очередного ребра <tex>e</tex> в <tex>F</tex> может привести к возникновению цикла в одной из компонент связности <tex>F</tex>. В этом случае, очевидно, <tex>e</tex> не может быть включено в <tex>F</tex>. В противном случае <tex>e</tex> соединяет разные компоненты связности <tex>F</tex>, тогда существует [[Лемма о безопасном ребре#Необходимые определения|разрез]] <tex> \langle S, T \rangle </tex> такой, что одна из компонент связности составляет одну его часть, а оставшаяся часть графа - вторую. Тогда <tex>e</tex> и есть минимальное ребро, пересекающее этот разрез. Значит, из [[Лемма о безопасном ребре|леммы о безопасном ребре]] следует, что <tex>F+e</tex> можно продолжить до MST, поэтому добавим это ребро в <tex>F</tex>.<br>
 
Несложно понять, что после выполнения такой процедуры получится остовное дерево, при этом его минимальность вытекает из леммы о безопасном ребре.
 
  
 
==Реализация==
 
==Реализация==
 +
'''Псевдокод второго прохода:
 +
{| width = 100%
 +
|-
 +
|
 +
  dfs(<tex>v, c, parent</tex>)
 +
      для всех  вершин u смежных v:
 +
            если (<tex>u</tex> родитель)
 +
                переходим к следующей итерации
 +
            если (<tex>u</tex> не посещена)
 +
                если (<tex>return[u] >= enter[v]</tex>)
 +
                    <tex>c2 \leftarrow</tex> новый цвет
 +
                    <tex>col[vu] \leftarrow c2</tex>
 +
                    dfs(<tex>u, c2, v</tex>)
 +
                иначе
 +
                    <tex>col[vu] \leftarrow c</tex>
 +
                    dfs(<tex>u, c, v</tex>)
 +
            иначе:
 +
                если (<tex>enter[u] <= enter[v]</tex>)
 +
                    <tex>col[vu] \leftarrow c</tex>         
 +
    start()
 +
        для всех v вершин графа:
 +
            если (<tex>v</tex> не посещена)
 +
                dfs(<tex>v, -1, -1</tex>)
 +
|width = "310px" |[[Файл:Vertex_doubleconnection_1.png‎‎|thumb|center|400px|Компоненты обозначены разным цветом]]
 +
|}
 +
 
<b>Вход</b>: граф <tex>G = (V, E)</tex><br>
 
<b>Вход</b>: граф <tex>G = (V, E)</tex><br>
 
<b>Выход</b>: минимальный остов <tex>F</tex> графа <tex>G</tex><br>
 
<b>Выход</b>: минимальный остов <tex>F</tex> графа <tex>G</tex><br>

Версия 00:43, 15 декабря 2012

Алгоритм Борувки — алгоритм поиска минимального остовного дерева (minimum spanning tree, MST) во взвешенном неориентированном связном графе. Впервые был опубликован в 1926 году Отакаром Борувкой.

Описание алгоритма

Пока [math]F[/math] не является деревом

  1. Для каждой компоненты связанности находим минимальное по весу ребро, которое связывает вершину из данной компоненты с вершиной, не принадлежащей данной компоненте.
  2. Добавим в [math]F[/math] все ребра, которые хотя бы для одной компоненты оказались минимальными.

Получившееся множество [math]F[/math] является минимальным остовным деревом графа [math]G[/math].


Реализация

Псевдокод второго прохода:

  dfs([math]v, c, parent[/math])
      для всех  вершин u смежных v:
           если ([math]u[/math] родитель) 
               переходим к следующей итерации
           если ([math]u[/math] не посещена)
               если ([math]return[u] \gt = enter[v][/math])
                   [math]c2 \leftarrow[/math] новый цвет
                   [math]col[vu] \leftarrow c2[/math]
                   dfs([math]u, c2, v[/math])
               иначе
                   [math]col[vu] \leftarrow c[/math]
                   dfs([math]u, c, v[/math])
           иначе:
               если ([math]enter[u] \lt = enter[v][/math])
                   [math]col[vu] \leftarrow c[/math]          
   start()
       для всех v вершин графа:
           если ([math]v[/math] не посещена)
               dfs([math]v, -1, -1[/math])
Компоненты обозначены разным цветом

Вход: граф [math]G = (V, E)[/math]
Выход: минимальный остов [math]F[/math] графа [math]G[/math]
1) [math]F := (V, \varnothing)[/math]
1) Отсортируем [math]E[/math] по весу ребер.
2) Заведем систему непересекающихся множеств (DSU) и инициализируем ее множеством [math]V[/math].
3) Перебирая ребра [math]uv \in EG[/math] в порядке увеличения веса, смотрим, принадлежат ли [math]u[/math] и [math]v[/math] одному множеству. Если нет, то объединяем множества, в которых лежат [math]u[/math] и [math]v[/math], и добавляем ребро [math]uv[/math] к [math]F[/math].

Асимптотика

Сортировка [math]E[/math] займет [math]O(E\log E)[/math].
Работа с DSU займет [math]O(E\alpha(V))[/math], где [math]\alpha[/math] - обратная функция Аккермана, которая не превосходит 4 во всех практических приложениях и которую можно принять за константу.
Алгоритм работает за [math]O(E(\log E+\alpha(V))) = O(E\log E) = O(E\log V^2) = O(E\log V)[/math].

Литература

  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

См. также