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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Алгоритм Крускала»)
Перейти к: навигация, поиск
Визуализация Алгоритма Краскала

Алгоритм Краскала — эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера[1].

Алгоритм описан Джозефом Краскалом (англ.) в 1956 году, этот алгоритм почти не отличается от aлгоритма Борувки предложенный Отакаром Борувкой[en] в 1926 году.

Формулировка[править | править код]

Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса. Подробное описание алгоритма можно найти в литературе[2].

Оценка[править | править код]

До начала работы алгоритма необходимо отсортировать рёбра по весу, это требует O(E × log(E)) времени. После чего компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(E × α(E, V)), где α — функция, обратная к функции Аккермана. Поскольку для любых практических задач α(E, V) < 5, то можно принять её за константу, таким образом, общее время работы алгоритма Краскала можно принять за O(E * log(E)).

Доказательство корректности алгоритма[править | править код]

Алгоритм Крускала действительно находит остовное дерево минимального веса, поскольку он является частным случаем алгоритма Радо — Эдмондса[3] для графического матроида, где независимые множества — ациклические множества рёбер.

Пример[править | править код]

Изображение Описание
Kruskal Algorithm 1.svg Ребра AD и CE имеют минимальный вес, равный 5. Произвольно выбирается ребро AD (выделено на рисунке).
Kruskal Algorithm 2.svg Теперь наименьший вес, равный 5, имеет ребро CE. Так как добавление CE не образует цикла, то выбираем его в качестве второго ребра.
Kruskal Algorithm 3.svg Аналогично выбираем ребро DF, вес которого равен 6.
Kruskal Algorithm 4.svg Следующие ребра — AB и BE с весом 7. Произвольно выбирается ребро AB, выделенное на рисунке. Ребро BD выделено красным, так как уже существует путь (зелёный) между B и D, поэтому, если бы это ребро было выбрано, то образовался бы цикл ABD.
Kruskal Algorithm 5.svg Аналогичным образом выбирается ребро BE, вес которого равен 7. На этом этапе красным выделено гораздо больше ребер: BC, потому что оно создаст цикл BCE, DE, потому что оно создаст цикл DEBA, и FE, потому что оно сформирует цикл FEBAD.
Kruskal Algorithm 6.svg Алгоритм завершается добавлением ребра EG с весом 9. Минимальное остовное дерево построено.

См. также[править | править код]

Примечания[править | править код]

  1. Дискретная математика, 2006, с. 307.
  2. Дискретная математика, 2006, с. 309-311.
  3. В. Е. Алексеев, В. А. Таланов, Графы и алгоритмы // Интуит.ру, 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
  • Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — 744 с. — ISBN 5-7038-2886-4.

Ссылки[править | править код]