Алгоритм Крускала
Алгоритм Крускала (или алгоритм Краскала) — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джозефом Крускалом в 1956 году.
Содержание |
[править] Формулировка
Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса.
[править] Оценка
До начала работы алгоритма необходимо отсортировать рёбра по весу, это требует O(E × log(E)) времени. После чего компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(E × α(E, V)), где α — функция, обратная к функции Аккермана. Поскольку для любых практических задач α(E, V) < 5, то можно принять её за константу, таким образом общее время работы алгоритма Крускала можно принять за O(E * log(E)).
[править] Доказательство корректности алгоритма
Алгоритм Крускала действительно находит остовное дерево минимального веса, поскольку он является частным случаем алгоритма Радо — Эдмондса[1] для графического матроида, где независимые множества — ациклические множества рёбер.
[править] Пример
| Изображение | Описание |
|---|---|
 |
Ребра AD и CE имеют минимальный вес, равный 5. Произвольно выбирается ребро AD (выделено на рисунке). |
 |
Теперь наименьший вес, равный 5, имеет ребро CE. Так как добавление CE не образует цикла, то выбираем его в качестве второго ребра. |
 |
Аналогично выбираем ребро DF, вес которого равен 6. |
 |
Следующие ребра — AB и BE с весом 7. Произвольно выбирается ребро AB, выделенное на рисунке. Ребро BD выделено красным, так уже существует путь (зеленый) между B и D, поэтому, если бы это ребро было выбрано, то образовался бы цикл ABD. |
 |
Аналогичным образом выбирается ребро BE, вес которого равен 7. На этом этапе красным выделено гораздо больше ребер: BC, потому что оно создаст цикл BCE, DE, потому что оно создаст цикл DEBA, и FE, потому что оно сформирует цикл FEBAD. |
 |
Алгоритм завершается добавлением ребра EG с весом 9. Минимальное остовное дерево построено. |
[править] См. также
[править] Примечания
- ↑ В.Е. Алексеев, В.А. Таланов, Графы и алгоритмы // Интуит.ру, 2006 - ISBN 5-9556-0066-3. 14. Лекция: Жадные алгоритмы и матроиды. Теорема Радо-Эдмондса.
[править] Литература
- Joseph. B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. // Proc. AMS. 1956. Vol 7, No. 1. C. 48-50
