Минимальные остовные деревья

В 1926 году Отакара Борувку попросили спланировать электросеть южной Моравии как можно дешевле. Его вопрос — как соединить все населенные пункты, использовав наименьшую общую длину линий, — это задача о минимальном остовном дереве, и у нее есть одни из самых простых и изящных решений во всей информатике.

Граф, у ребер которого есть длины: выделены короткие ребра растущего дерева, пропущенное ребро, которое замкнуло бы цикл, показано красным пунктиром, а внизу — список ребер, которые еще осталось проверить
Граф, у ребер которого есть длины: выделены короткие ребра растущего дерева, пропущенное ребро, которое замкнуло бы цикл, показано красным пунктиром, а внизу — список ребер, которые еще осталось проверить

Задача

Возьмите связный граф, у ребер которого есть длины, или стоимости. Остовное дерево — это набор ребер, который соединяет все вершины и не содержит циклов; при n вершинах в нем всегда ровно n − 1 ребер, потому что каждое ребро присоединяет еще одну вершину. Среди всех остовных деревьев у минимального остовного дерева наименьшая общая длина. У графа может быть огромное число остовных деревьев, но перебирать их все не нужно.

Почему жадный подход работает

Разделите вершины на две группы любым способом. Самое короткое ребро между группами всегда входит в какое-нибудь минимальное остовное дерево: если бы дерево использовало вместо него более длинное ребро между группами, замена на более короткое соединила бы те же вершины дешевле. Это свойство разреза. Обратная сторона медали — свойство цикла: самое длинное ребро любого цикла никогда не нужно. Оба алгоритма ниже просто раз за разом применяют эти правила.

Пример

Возьмите ребра A–B длиной 1, B–C 2, A–C 3, C–D 4 и B–D 5. Алгоритм Краскала берет A–B, затем B–C, затем пропускает A–C, потому что A и C уже связаны и это ребро замкнуло бы цикл, затем берет C–D. В дереве три ребра на четыре вершины, значит, оно готово, общая длина 7, а до B–D дело даже не доходит. Алгоритм Прима от A сначала добавляет B по A–B; ребро B–C (2) из B выигрывает у A–C (3) как путь к C, поэтому C присоединяется по B–C; ребро C–D (4) из C выигрывает у B–D (5), поэтому D присоединяется по C–D. То же дерево, те же 7.

Краскал, Прим и Борувка

Алгоритм Краскала, опубликованный Джозефом Краскалом в 1956 году, сортирует ребра и с помощью системы непересекающихся множеств пропускает ребра внутри одной части, поэтому его работа растет как E log E. Алгоритм Прима первым описал Войтех Ярник в 1930 году, а заново открыли Роберт Прим в 1957 году и Эдсгер Дейкстра в 1959 году; с двоичной кучей его работа растет как E log V, а с простым массивом — как V², что хорошо для плотных графов. Алгоритм Борувки 1926 года позволяет каждой части одновременно взять свое самое короткое исходящее ребро, что удобно для параллельных компьютеров.

Отакар Борувка в 1981 году. В 1926 году его попросили как можно дешевле спланировать электросеть южной Моравии, и он дал первый алгоритм минимального остовного дерева.
Отакар Борувка в 1981 году. В 1926 году его попросили как можно дешевле спланировать электросеть южной Моравии, и он дал первый алгоритм минимального остовного дерева.

Применения

С помощью минимальных остовных деревьев проектируют дешевые сети кабелей, труб и дорог. Они делят данные на кластеры: удалите самые длинные ребра дерева, и оставшиеся части будут кластерами. Они дают быстрый маршрут для задачи коммивояжера, не более чем вдвое длиннее лучшего, если расстояния подчиняются неравенству треугольника. А алгоритм Краскала или Прима на сетке со случайными длинами ребер — классический способ построить лабиринт.

Попробуйте сами

Откройте приложение, выберите Краскала или Прима и нажмите Шаг. У Краскала ребра, которые еще осталось проверить, перечислены под графом от самого короткого к самому длинному; ребра, которые замкнули бы цикл, нарисованы красным пунктиром. У Прима там перечислены вершины, ожидающие присоединения, с длиной их лучшего ребра, которое нарисовано пунктиром. Запустите оба на одном графе и сравните: порядок разный, но общая длина всегда одна и та же.

Часто задаваемые вопросы

Сколько ребер в остовном дереве?

Ровно на одно меньше, чем вершин. Меньшим числом ребер нельзя соединить все вершины, а еще одно ребро всегда создало бы цикл.

Что быстрее, Краскал или Прим?

Алгоритм Краскала, который сортирует ребра, обычно проще и быстр на разреженных графах с небольшим числом ребер. Алгоритм Прима с кучей хорошо работает на плотных графах, а с обычным массивом ему нужно около V² шагов независимо от числа ребер.

Что такое union-find?

Структура данных (система непересекающихся множеств), которая следит, какие вершины находятся в одной части. Она отвечает на вопрос «связаны ли эти две?» и почти мгновенно объединяет две части — именно это нужно алгоритму Краскала для каждого ребра.

Подходит ли минимальное остовное дерево для ориентированных графов?

Не напрямую. Для графов с односторонними ребрами соответствующая задача — минимальное остовное ориентированное дерево (арборесценция), которое находит алгоритм Чу — Лю/Эдмондса (Chu–Liu/Edmonds).

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Построить минимальное остовное дерево