Алгоритм Борувки — различия между версиями
Novik (обсуждение | вклад) м (→Реализация) |
|||
Строка 41: | Строка 41: | ||
'''for''' <tex>\mathtt{(u,v)} \in E </tex> | '''for''' <tex>\mathtt{(u,v)} \in E </tex> | ||
'''if''' <tex>\mathtt{u.comp} \neq \mathtt{v.comp}</tex> | '''if''' <tex>\mathtt{u.comp} \neq \mathtt{v.comp}</tex> | ||
− | '''if''' <tex>w(\mathtt{minEdge}[\mathtt{u.comp}]) | + | '''if''' <tex>w(\mathtt{minEdge}[\mathtt{u.comp}]) > w(u,v)</tex> |
<tex>\mathtt{minEdge}[\mathtt{u.comp}] = (u,v)</tex> | <tex>\mathtt{minEdge}[\mathtt{u.comp}] = (u,v)</tex> | ||
− | '''if''' <tex>w(\mathtt{minEdge}[\mathtt{v.comp}]) | + | '''if''' <tex>w(\mathtt{minEdge}[\mathtt{v.comp}]) > w(u,v)</tex> |
<tex>\mathtt{minEdge}[\mathtt{v.comp}] = (u,v)</tex> | <tex>\mathtt{minEdge}[\mathtt{v.comp}] = (u,v)</tex> | ||
'''for''' <tex>k \in </tex> Component | '''for''' <tex>k \in </tex> Component |
Версия 20:42, 1 сентября 2019
Алгоритм Борувки (англ. Borůvka's algorithm) — алгоритм поиска минимального остовного дерева во взвешенном неориентированном связном графе. Впервые был опубликован в 1926 году Отакаром Борувкой.
Содержание
Описание алгоритма
Алгоритм состоит из нескольких шагов:
- Изначально каждая вершина графа — тривиальное дерево, а ребра не принадлежат никакому дереву.
- Для каждого дерева найдем минимальное инцидентное ему ребро. Добавим все такие ребра.
- Повторяем шаг пока в графе не останется только одно дерево .
Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес каждого ребра равен один. В могут быть добавлены все три ребра. Избежать эту проблему можно, например, выбирая в первом пункте среди ребер, равных по весу, ребро с наименьшим номером.
Доказательство корректности
Теорема: |
Алгоритм Борувки строит MST. |
Доказательство: |
Очевидно, что в результате работы алгоритма получается дерево. Пусть — минимальное остовное дерево графа , а — дерево полученное после работы алгоритма.Покажем, что .Предположим обратное Понятно, что в момент, когда ребро . Пусть ребро — первое добавленное ребро дерева , не принадлежащее дереву . Пусть — путь, соединяющий в дереве вершины ребра . добавляли, какое-то ребро (назовем его ) не было добавлено. По алгоритму . Однако тогда — остовное дерево веса не превышающего вес дерева . Получили противоречение. Следовательно . |
Реализация
У вершины есть поле
— компонента связности, которой принадлежит эта вершина.
//— исходный граф // — весовая функция function while for Component // Component — множество компонент связности в . Для // каждой компоненты связности вес минимального ребра = . // Разбиваем граф на компоненты связности обычным dfs-ом. for if if if for Component // Добавляем ребро, если его не было в return |
Пример
Асимптотика
На
-ой итерации внешнего цикла каждая компонента состоит как минимум из двух компонент из -й итерации. Значит, на каждой итерации число компонент уменьшается как минимум в раза. Тогда внешний цикл повторяется раз, так как количество компонент изначально равно количеству вершин. Что же касается внутреннего цикла, то он выполняется за , где — количество рёбер в исходном графе. Следовательно конечное время работы алгоритма .