Алгоритм Краскала — различия между версиями
(→Задача о максимальном ребре минимального веса) |
(→Реализация) |
||
Строка 9: | Строка 9: | ||
<font color=green>// для проверки возможности добавления ребра используется система непересекающихся множеств</font> | <font color=green>// для проверки возможности добавления ребра используется система непересекающихся множеств</font> | ||
'''function''' <tex>\mathtt{kruskalFindMST}():</tex> | '''function''' <tex>\mathtt{kruskalFindMST}():</tex> | ||
− | <tex> \mathtt{F}\ | + | <tex> \mathtt{F} \leftarrow V(G)</tex> |
<tex>\mathtt{sort}(E(G))\</tex> | <tex>\mathtt{sort}(E(G))\</tex> | ||
'''for''' <tex>vu \in E(G)</tex> | '''for''' <tex>vu \in E(G)</tex> |
Версия 12:56, 20 ноября 2014
Алгоритм Краскала (англ. Kruskal's algorithm) — алгоритм поиска минимального остовного дерева (англ. minimum spanning tree, MST) во взвешенном неориентированном связном графе.
Содержание
Идея
Будем последовательно строить подграф разрез такой, что одна из компонент связности составляет одну его часть, а оставшаяся часть графа — вторую. Тогда и есть минимальное ребро, пересекающее этот разрез. Значит, из леммы о безопасном ребре следует, что можно продолжить до MST, поэтому добавим это ребро в .
Реализация
//— исходный граф // — минимальный остов // для проверки возможности добавления ребра используется система непересекающихся множеств function for if и в разных компонентах связности
Задача о максимальном ребре минимального веса
Очевидно, что максимальное ребро в MST минимально. Пусть это не так, тогда рассмотрим разрез, который оно пересекает. В этом разрезе должно быть ребро с меньшим весом, иначе максимальное ребро было бы минимальным, но в таком случае минимальный остов не является минимальным, следовательно, максимальное ребро в минимальном остовном дереве минимально. Если же максимальное ребро в остовном дереве минимально, то такое дерево может не быть минимальным. Зато его можно найти быстрее чем MST, а конкретно за алгоритма поиска k-ой порядковой статистики найдем за ребро-медиану и разделим множество ребер на два подмножества, так чтобы в первом подмножестве ребра были меньше медианы, а во втором больше. Проверим образуют ли ребра из первого подмножества остов, просто запустив обход в глубину за . Если да, то удалим все ребра, которые больше медианы, и запустим алгоритм от первого подмножества. Иначе сожмем компоненты связности в супервершины, рассмотрим новый граф с такими вершинами и оставшимися ребрами, то есть ребрами, которые соединяют компоненты связности старого графа.
На каждой итерации остается половина ребер, следовательно, время работы алгоритма .
Пример
Задан неориентированный связный граф, требуется построить в нём минимальное остовное дерево.
Создадим новый граф, содержащий все вершины из заданного графа, но не содержащий рёбер.
Этот новый граф будет ответом, в него будут добавлены рёбра из заданного графа по ходу выполнения алгоритма.
Отсортируем рёбра заданного графа по их весам и рассмотрим их в порядке возрастания.
Рёбра (в порядке их просмотра) | ae | cd | ab | be | bc | ec | ed |
Веса рёбер |
Асимптотика
Сортировка
Работа с системой непересекающихся множеств займет , где — обратная функция Аккермана, которая не превосходит 4 во всех практических приложениях и которую можно принять за константу.
Алгоритм работает за .
См. также
Источники информации
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
- Википедия — Функция Аккермана
- Википедия — Алгоритм Крускала
- Wikipedia — Kruskal's algorithm
- MAXimal :: algo :: Минимальное остовное дерево. Алгоритм Крускала