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

Алгоритм описан в 1956 году , этот алгоритм почти не отличается от алгоритма Борувки , предложенного в 1926 году.

Формулировка

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

Оценка

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

Доказательство корректности алгоритма

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

Пример

Изображение	Описание
	Ребра AD и CE имеют минимальный вес, равный 5. Произвольно выбирается ребро AD (выделено на рисунке). В результате получаем множество выбранных вершин ( A , D ).
	Теперь наименьший вес, равный 5, имеет ребро CE . Так как добавление CE не образует цикла, то выбираем его в качестве второго ребра. Так как это ребро не имеет общих вершин с имеющимся множеством выбранных вершин ( A , D ), получаем второе множество выбранных вершин ( C , E ).
	Аналогично выбираем ребро DF , вес которого равен 6. При этом не возникает ни одного цикла, так как не существует (среди невыбранных) ребра, имеющего обе вершины из одного ( A , D , F ) или второго ( C , E ) множества выбранных вершин.
	Следующие ребра — AB и BE с весом 7. Произвольно выбирается ребро AB , выделенное на рисунке. Тем самым вершина B добавляется к первому множеству выбранных вершин ( A , B , D , F ). Невыбранное ранее ребро BD выделено красным, так как его вершины входят в множество выбранных вершин ( A , B , D , F ), а, следовательно, уже существует путь (зелёный) между B и D (если бы это ребро было выбрано, то образовался бы цикл ABD ). Следующее ребро может быть выбрано только после нахождения всех циклов.
	Аналогичным образом выбирается ребро BE , вес которого равен 7. Так как это ребро имеет вершины в обоих множествах выбранных вершин ( A , B , D , F ) и ( C , E ), эти множества объединяются в одно ( A , B , C , D , E , F ). На этом этапе красным выделено гораздо больше ребер, так как множества выбранных вершин, а, следовательно, и множества выбранных рёбер объединились. Теперь BC создаст цикл BCE , DE создаст цикл DEBA , и FE сформирует цикл FEBAD .
	Алгоритм завершается добавлением ребра EG с весом 9. Количество выбранных вершин ( A , B , C , D , E , F , G ) = 7 соответствует количеству вершин графа. Минимальное остовное дерево построено.

См. также

• Минимальное остовное дерево
• Остовное дерево
• Алгоритм Борувки
• Алгоритм Прима

Примечания

Литература

• 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 .

Ссылки