Алгоритм Краскала — различия между версиями
(→Асимптотика) |
(→Задача о максимальном ребре минимального веса) |
||
Строка 21: | Строка 21: | ||
Описанный далее алгоритм ищет максимальное ребро минимального веса и одновременно строит остовное дерево. С помощью [[Поиск_k-ой_порядковой_статистики_за_линейное_время | алгоритма поиска k-ой порядковой статистики]] найдем ребро-медиану за <tex>O(E)</tex> и разделим множество ребер на два равных по мощности подмножества так, чтобы в первом ребра не превосходили медиану, а во втором были не меньше ее. Проверим образуют ли ребра из первого подмножества остов графа, запустив [[Использование_обхода_в_глубину_для_проверки_связности|обход в глубину]]. | Описанный далее алгоритм ищет максимальное ребро минимального веса и одновременно строит остовное дерево. С помощью [[Поиск_k-ой_порядковой_статистики_за_линейное_время | алгоритма поиска k-ой порядковой статистики]] найдем ребро-медиану за <tex>O(E)</tex> и разделим множество ребер на два равных по мощности подмножества так, чтобы в первом ребра не превосходили медиану, а во втором были не меньше ее. Проверим образуют ли ребра из первого подмножества остов графа, запустив [[Использование_обхода_в_глубину_для_проверки_связности|обход в глубину]]. | ||
* Если да, то рекурсивно запустим алгоритм от него. | * Если да, то рекурсивно запустим алгоритм от него. | ||
− | * В противном случае просмотрим ребра в нем, если текущее ребро соединяет разные компоненты связности (проверим с помощью | + | * В противном случае просмотрим ребра в нем, если текущее ребро соединяет разные компоненты связности (проверим с помощью СНМ за <tex>O(1)</tex>), то добавим его в остов. Запустим алгоритм от несвязных компонент и ребер второго подмножества. |
На последнем шаге останутся две компоненты связности и одно ребро в первом подмножестве — это максимальное ребро минимального веса, добавим его в остов. Получившийся остов может не быть минимальным, но все ребра в нем не превосходят по весу ребра, которое мы нашли. | На последнем шаге останутся две компоненты связности и одно ребро в первом подмножестве — это максимальное ребро минимального веса, добавим его в остов. Получившийся остов может не быть минимальным, но все ребра в нем не превосходят по весу ребра, которое мы нашли. | ||
Версия 16:27, 17 декабря 2014
Алгоритм Краскала (англ. Kruskal's algorithm) — алгоритм поиска минимального остовного дерева (англ. minimum spanning tree, MST) во взвешенном неориентированном связном графе.
Содержание
Идея
Будем последовательно строить подграф разрез такой, что одна из компонент связности составляет одну его часть, а оставшаяся часть графа — вторую. Тогда — минимальное ребро, пересекающее этот разрез. Значит, из леммы о безопасном ребре следует, что является безопасным, поэтому добавим это ребро в . На последнем шаге ребро соединит две оставшиеся компоненты связности, полученный подграф будет минимальным остовным деревом графа . Для проверки возможности добавления ребра используется система непересекающихся множеств.
графа ("растущий лес"), пытаясь на каждом шаге достроить до некоторого MST. Начнем с того, что включим в все вершины графа . Теперь будем обходить множество в порядке неубывания весов ребер. Если очередное ребро соединяет вершины одной компоненты связности , то добавление его в остов приведет к возникновению цикла в этой компоненте связности. В таком случае, очевидно, не может быть включено в . Иначе соединяет разные компоненты связности , тогда существуетРеализация
//— исходный граф // — минимальный остов function for if и в разных компонентах связности return
Задача о максимальном ребре минимального веса
Легко показать, что максимальное ребро в MST минимально. Обратное в общем случае неверно. Но MST из-за сортировки строится за
. Однако из-за того, что необходимо минимизировать только максимальное ребро, а не сумму всех рёбер, можно предъявить алгоритм, решающий задачу за линейное время.Описанный далее алгоритм ищет максимальное ребро минимального веса и одновременно строит остовное дерево. С помощью алгоритма поиска k-ой порядковой статистики найдем ребро-медиану за и разделим множество ребер на два равных по мощности подмножества так, чтобы в первом ребра не превосходили медиану, а во втором были не меньше ее. Проверим образуют ли ребра из первого подмножества остов графа, запустив обход в глубину.
- Если да, то рекурсивно запустим алгоритм от него.
- В противном случае просмотрим ребра в нем, если текущее ребро соединяет разные компоненты связности (проверим с помощью СНМ за ), то добавим его в остов. Запустим алгоритм от несвязных компонент и ребер второго подмножества.
На последнем шаге останутся две компоненты связности и одно ребро в первом подмножестве — это максимальное ребро минимального веса, добавим его в остов. Получившийся остов может не быть минимальным, но все ребра в нем не превосходят по весу ребра, которое мы нашли.
На каждом шаге ребер становится в два раза меньше, а все операции выполняются за время пропорциональное количеству ребер на текущем шаге, тогда время работы алгоритма
.Пример
Рёбра (в порядке их просмотра) | ae | cd | ab | be | bc | ec | ed |
Веса рёбер |
Асимптотика
Сортировка
Работа с СНМ займет , где — обратная функция Аккермана, которая не превосходит во всех практических приложениях и которую можно принять за константу.
Алгоритм работает за .
См. также
Источники информации
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
- Википедия — Функция Аккермана
- Википедия — Алгоритм Крускала
- Wikipedia — Kruskal's algorithm
- MAXimal :: algo :: Минимальное остовное дерево. Алгоритм Крускала