- Текущая
- В дереве
- Замкнуло бы цикл
Алгоритм Краскала
Алгоритм Краскала строит минимальное остовное дерево — самый дешевый набор ребер, соединяющий все вершины, — самым простым из мыслимых способов: берите ребра от самого короткого к самому длинному и оставляйте каждое, если только оно не замыкает цикл. Пройдите по шагам и посмотрите, как отдельные части растут и сливаются в одно дерево и какие ребра пропускаются. Нажмите Пуск, чтобы посмотреть, как растет дерево, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Число на каждом ребре — его длина. Под графом — ребра, которые еще осталось проверить, от самого короткого к самому длинному; ребро, концы которого уже связаны, замкнуло бы цикл и нарисовано красным пунктиром. Кнопка Новый граф создает другой граф; выберите, сколько в нем вершин и ребер. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.
Как это работает
- Нажмите Пуск или используйте Шаг и Назад, чтобы идти по одному шагу.
- Перетащите ползунок шагов, чтобы перейти в любое место. Ребра, которые еще осталось проверить, перечислены под графом, от самого короткого.
- Обратите внимание на ребра, нарисованные красным пунктиром: они замкнули бы цикл. Кнопка Новый граф создает другой граф для пробы.
Как работает алгоритм Краскала
Отсортируйте все ребра от самого короткого к самому длинному. Вначале каждая вершина — отдельная часть. Проверяйте ребра по порядку: если ребро соединяет две разные части, оно входит в дерево, и эти части становятся одной; если оба его конца уже в одной части, оно замкнуло бы цикл, поэтому пропустите его. Остановитесь, когда все станет одной частью. Это происходит после того, как добавлено на одно ребро меньше, чем вершин, часто задолго до проверки последнего ребра.
Система непересекающихся множеств
Для каждого ребра алгоритм Краскала должен спросить, связаны ли уже его концы. Система непересекающихся множеств (union-find) отвечает на это быстро: у каждой части есть один представитель, find идет по ссылкам к нему, а union подвешивает одного представителя к другому. С двумя простыми приемами, сжатием путей и объединением по размеру, каждый вопрос занимает почти постоянное время, поэтому медленнее всего сортировка ребер: работа растет как E log E.
Часто задаваемые вопросы
Что такое алгоритм Краскала?
Жадный алгоритм, который строит минимальное остовное дерево: сортирует все ребра от самого короткого к самому длинному и добавляет каждое ребро, которое не замыкает цикл с уже выбранными ребрами.
Как алгоритм Краскала обнаруживает цикл?
Ребро замыкает цикл ровно тогда, когда его концы уже связаны выбранными ребрами. Система непересекающихся множеств следит, какие вершины связаны, и отвечает на этот вопрос почти мгновенно.
Почему алгоритм Краскала работает?
Благодаря свойству цикла: самое длинное ребро любого цикла никогда не нужно для минимального остовного дерева. Каждое ребро, которое пропускает Краскал, — самое длинное в цикле, который оно замкнуло бы, ведь все ребра до него были короче или такой же длины.
Когда использовать Краскала вместо Прима?
Алгоритм Краскала прост и быстр на разреженных графах и работает прямо с обычным списком ребер. Алгоритм Прима подходит для плотных графов и графов, хранящихся в виде списков смежности. Оба находят дерево одной и той же общей длины.
Отправляется ли мой граф куда-нибудь?
Нет. Граф создается и дерево строится в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор