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

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

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

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

Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса. Подробное описание алгоритма приведено в книге[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 выделено красным, так как уже существует путь (зеленый) между A и 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.

Ссылки[править | править вики-текст]