Алгоритм Краскала, также алгоритм Крускала[1][2][3][4] — эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера[5].
Алгоритм описан Джозефом Краскалом в 1956 году, этот алгоритм почти не отличается от алгоритма Борувки, предложенного Отакаром Борувкой в 1926 году.
Формулировка править
В начале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса. Подробное описание алгоритма можно найти в литературе[6].
Оценка править
До начала работы алгоритма необходимо отсортировать рёбра по весу, это требует O(E × log(E)) времени. После чего компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(E × α(E, V)), где α — функция, обратная к функции Аккермана. Поскольку для любых практических задач α(E, V) < 5, то можно принять её за константу, таким образом, общее время работы алгоритма Краскала можно принять за O(E * log(E)).
Доказательство корректности алгоритма править
Алгоритм Краскала действительно находит остовное дерево минимального веса, поскольку он является частным случаем алгоритма Радо — Эдмондса[7] для графического матроида, где независимые множества — ациклические множества рёбер.
Пример править
| Изображение | Описание |
|---|---|
|
Ребра 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 соответствует количеству вершин графа. Минимальное остовное дерево построено. |
См. также править
Примечания править
- ↑ А. В. Ахо, Структуры данных и алгоритмы, 2000
- ↑ Кормен и др., Алгоритмы. Построение и анализ, 2005
- ↑ А. Левитин, Алгоритмы. Введение в разработку и анализ, 2006
- ↑ Хопкрофт и др., Введение в теорию автоматов, языков и вычислений, 2002
- ↑ Дискретная математика, 2006, с. 307.
- ↑ Дискретная математика, 2006, с. 309-311.
- ↑ В. Е. Алексеев, В. А. Таланов, Графы и алгоритмы // Интуит.ру, 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.