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

Алгоритм Борувки — это алгоритм нахождения минимального остовного дерева (МОД) во взвешенном неориентированном графе. Относится к классу жадных алгоритмов и работает по принципу параллельного добавления рёбер минимального веса, инцидентных каждой вершине или компоненте связности, до тех пор, пока не будет построено остовное дерево. Алгоритм был впервые опубликован в 1926 году чешским математиком Отакаром Борувкой для решения задачи электрификации Моравии.

История

Алгоритм был разработан в 1926 году чешским математиком Отакаром Борувкой (Otakar Borůvka) по заказу правительства Моравии (ныне часть Чехии). Задача состояла в построении максимально экономичной электрической сети, соединяющей все населённые пункты региона. Борувка предложил метод, который позволял минимизировать общую длину проводов, используя только локальную информацию о расстояниях между ближайшими точками. В 1926 году работа была опубликована в чешском журнале «Elektrotechnický obzor» под названием «O jistém problému minimálním» («О некоторой минимальной задаче»).

В 1930 году польский математик Войцех Ярник (Wojciech Jarník) независимо переоткрыл алгоритм, а в 1957 году американский математик Роберт Прайм (Robert C. Prim) опубликовал его упрощённую версию, которая стала известна как алгоритм Прима. Тем не менее, алгоритм Борувки считается первым в истории алгоритмом для нахождения минимального остовного дерева. В 1960-х годах алгоритм был адаптирован для параллельных вычислений, что сделало его особенно полезным для работы с большими графами на многопроцессорных системах.

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

Алгоритм Борувки работает итеративно, на каждом шаге объединяя компоненты связности. Исходно каждая вершина графа считается отдельной компонентой. На каждой итерации для каждой компоненты выбирается ребро минимального веса, соединяющее её с другой компонентой. Затем все выбранные рёбра добавляются к строящемуся остовному дереву, и компоненты сливаются. Процесс повторяется до тех пор, пока не останется одна компонента, содержащая все вершины.

Формальное описание

1. Инициализация: пусть \( G = (V, E) \) — взвешенный неориентированный граф с \( |V| = n \) вершинами и \( |E| = m \) рёбрами. Пусть \( T \) — пустое множество рёбер будущего остовного дерева. Пусть \( C \) — множество компонент связности, где каждая вершина \( v \in V \) образует отдельную компоненту.
2. Пока количество компонент \( |C| > 1 \):

• Для каждой компоненты \( c \in C \) найти ребро \( e_c \) минимального веса, соединяющее вершину из \( c \) с вершиной из другой компоненты \( c' \neq c \). Если таких рёбер несколько, выбирается любое (например, с наименьшим номером).
• Добавить все найденные рёбра \( e_c \) в \( T \). При этом, если ребро уже было добавлено на предыдущих шагах, оно не добавляется повторно.
• Объединить компоненты, соединённые добавленными рёбрами, в новые компоненты.

1. Вернуть \( T \) как минимальное остовное дерево.

Пример работы

Рассмотрим граф с 4 вершинами (A, B, C, D) и рёбрами: AB (вес 1), AC (вес 3), AD (вес 4), BC (вес 2), BD (вес 5), CD (вес 6).

• Итерация 1: компоненты: {A}, {B}, {C}, {D}. Для A: минимальное ребро — AB (1). Для B: минимальное ребро — AB (1) или BC (2) — выбирается AB (1). Для C: минимальное ребро — BC (2). Для D: минимальное ребро — AD (4). Добавляются рёбра AB, BC, AD. Компоненты сливаются: {A, B, C} и {D}.
• Итерация 2: компоненты: {A, B, C} и {D}. Для {A, B, C}: минимальное ребро, соединяющее с {D} — AD (4) или BD (5) или CD (6) — выбирается AD (4). Для {D}: минимальное ребро — AD (4). Добавляется AD (уже есть). Компоненты сливаются: {A, B, C, D}.
• Итерация 3: одна компонента — алгоритм завершён. Остовное дерево: AB, BC, AD (суммарный вес 1+2+4=7).

Свойства и корректность

Алгоритм Борувки гарантированно находит минимальное остовное дерево для любого связного взвешенного неориентированного графа. Корректность доказывается через свойство разреза: на каждом шаге выбираемое ребро является минимальным для некоторого разреза графа, что соответствует критерию оптимальности. Алгоритм не зависит от порядка выбора рёбер при равенстве весов, хотя в случае неоднозначности может быть получено несколько различных МОД.

Сложность

Время работы алгоритма Борувки зависит от реализации. В базовом варианте для графа с \( n \) вершинами и \( m \) рёбрами каждая итерация требует \( O(m) \) операций для поиска минимальных рёбер для каждой компоненты. Количество итераций составляет \( O(\log n) \), так как на каждой итерации число компонент уменьшается как минимум вдвое. Таким образом, общая сложность составляет \( O(m \log n) \).

С использованием более эффективных структур данных, таких как система непересекающихся множеств (DSU) и сортировка рёбер, сложность может быть снижена до \( O(m \log n) \) в худшем случае. Для разреженных графов (\( m = O(n) \)) алгоритм работает за \( O(n \log n) \). Алгоритм хорошо поддаётся параллелизации, что делает его привлекательным для распределённых вычислений.

Применение

Алгоритм Борувки применяется в задачах, где требуется построение минимального остовного дерева, особенно в параллельных и распределённых вычислительных средах. Основные области использования:

• Проектирование сетей: электрические сети, телекоммуникационные сети, трубопроводы. Алгоритм позволяет минимизировать стоимость соединения узлов.
• Кластеризация данных: в задачах машинного обучения и анализа данных, где минимальное остовное дерево используется для выделения кластеров.
• Компьютерное зрение: для сегментации изображений на основе графов.
• Распределённые алгоритмы: алгоритм Борувки лежит в основе некоторых протоколов маршрутизации в децентрализованных сетях, например, в протоколе STP (Spanning Tree Protocol) для предотвращения петель в Ethernet-сетях.

Сравнение с другими алгоритмами

Алгоритм Борувки, наряду с алгоритмами Прима и Краскала, является одним из классических методов нахождения МОД. Основные отличия:

• Алгоритм Прима (1957) строит дерево, начиная с одной вершины, и на каждом шаге добавляет ребро минимального веса, соединяющее текущее дерево с остальными вершинами. Сложность \( O(m \log n) \) с использованием кучи.
• Алгоритм Краскала (1956) сортирует все рёбра по весу и добавляет их, если они не образуют цикл. Сложность \( O(m \log m) \) из-за сортировки.
• Алгоритм Борувки (1926) работает параллельно, на каждой итерации обрабатывая все компоненты. Его сложность \( O(m \log n) \), но он лучше подходит для параллельных вычислений.

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

Интересные факты

• Алгоритм Борувки был опубликован за 30 лет до алгоритмов Прима и Краскала, но долгое время оставался малоизвестным за пределами Чехословакии.
• В 1960-х годах алгоритм был переоткрыт независимо несколькими исследователями, включая Джорджа Дэвида Биркгофа и Джеймса Мак-Кирнана.
• Алгоритм Борувки является одним из немногих алгоритмов, который может быть эффективно реализован в модели распределённых вычислений, где каждый узел знает только о своих соседях.

Источники

• Borůvka, O. (1926). O jistém problému minimálním. Elektrotechnický obzor, 15, 153–164.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Kleinberg, J., & Tardos, É. (2006). Algorithm Design. Addison-Wesley.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.