Алгоритм Краскала

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

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

Идея

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

По шагам

Отсортируйте ребра от самого короткого к самому длинному. Проверяйте их в этом порядке. Если два конца ребра лежат в разных частях, добавьте его в дерево: две части становятся одной. Если оба конца уже в одной части, ребро замкнуло бы цикл, поэтому пропустите его. При n вершинах дерево готово после n − 1 ребер, а остальные ребра можно вообще не смотреть.

Пример

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

Система непересекающихся множеств

Единственный трудный вопрос, который задает алгоритм Краскала: находятся ли эти две вершины уже в одной части? На него отвечает система непересекающихся множеств (union-find). Каждая часть — маленькое дерево ссылок, ведущих к представителю. Find идет по ссылкам к представителю; union подвешивает одного представителя под другого. Сжатие путей, при котором каждая посещенная вершина начинает указывать прямо на представителя, и объединение по размеру делают ссылки такими короткими, что каждый вопрос занимает почти постоянное время.

История и скорость

Джозеф Краскал опубликовал алгоритм в 1956 году в короткой статье в журнале Proceedings of the American Mathematical Society. Медленнее всего сортировка ребер, поэтому работа растет как E log E для E ребер. Если ребра уже отсортированы или их длины — небольшие целые числа, алгоритм работает почти за линейное время.

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

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

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

Зачем алгоритм Краскала сортирует ребра?

Чтобы каждое добавляемое ребро было самым коротким из тех, что еще соединяют две части. Этот жадный выбор всегда безопасен благодаря свойству разреза, а каждое пропущенное ребро — самое длинное в цикле, который оно замкнуло бы, поэтому оно никогда не нужно.

Что такое система непересекающихся множеств?

Другое название union-find: структура, которая хранит набор отдельных множеств, здесь — части растущего леса, и умеет быстро сказать, к какому множеству относится элемент, и объединить два множества.

Работает ли алгоритм Краскала на несвязном графе?

Да. Он просто заканчивает с одним деревом для каждой связной части графа — минимальным остовным лесом, потому что никакое ребро не может соединить несвязанные части.

Используется ли алгоритм Краскала для чего-то еще?

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

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

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

Попробовать алгоритм Краскала