Алгоритм Краскала — эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера[1].
Алгоритм описан Джозефом Краскалом в 1956 году, этот алгоритм почти не отличается от aлгоритма Борувки предложенный Отакаром Борувкой[en] в 1926 году.
Формулировка
Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса. Подробное описание алгоритма можно найти в литературе[2].
Оценка
До начала работы алгоритма необходимо отсортировать рёбра по весу, это требует O(E × log(E)) времени. После чего компоненты связности удобно хранить в виде системы непересекающихся множеств. Все операции в таком случае займут O(E × α(E, V)), где α — функция, обратная к функции Аккермана. Поскольку для любых практических задач α(E, V) < 5, то можно принять её за константу, таким образом, общее время работы алгоритма Краскала можно принять за O(E * log(E)).
Доказательство корректности алгоритма
Алгоритм Краскала действительно находит остовное дерево минимального веса, поскольку он является частным случаем алгоритма Радо — Эдмондса[3] для графического матроида, где независимые множества — ациклические множества рёбер.
Пример
| Изображение | Описание |
|---|---|
 |
Ребра 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, с. 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.
Ссылки
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .