Алгоритм Крускала - Kruskal's algorithm
Алгоритмы поиска по графам и деревьям |
---|
Списки |
похожие темы |
Алгоритм Краскала находит минимальный остовный лес неориентированного взвешенного по ребрам графа . Если граф связан , он находит минимальное остовное дерево . (Минимальное остовное дерево связного графа - это подмножество ребер, которое формирует дерево, включающее каждую вершину , где сумма весов всех ребер в дереве минимизирована. Для несвязного графа минимальный остовной лес равен состоит из минимального остовного дерева для каждого связного компонента .) Это жадный алгоритм в теории графов, так как на каждом шаге он добавляет следующее ребро с наименьшим весом, которое не будет формировать цикл, к минимальному остовному лесу.
Этот алгоритм впервые появился в Proceedings of the American Mathematical Society , pp. 48–50 в 1956 году и был написан Джозефом Крускалом .
Другие алгоритмы для этой задачи включают в себя алгоритм Примы , на обратном удаление алгоритма и алгоритм борувки .
Алгоритм
- создать лес F (набор деревьев), где каждая вершина в графе представляет собой отдельное дерево
- создать набор S, содержащий все ребра в графе
- в то время как S является непустым и F еще не охватывает
- удалить кромку с минимальным весом из S
- если удаленное ребро соединяет два разных дерева, добавьте его в лес F , объединив два дерева в одно дерево
По завершении алгоритма лес образует минимальный остовный лес графа. Если граф связан, лес состоит из одного компонента и образует минимальное остовное дерево.
Псевдокод
Следующий код реализован с несвязной структурой данных . Здесь мы представляем наш лес F как набор ребер и используем структуру данных с непересекающимся набором, чтобы эффективно определять, являются ли две вершины частью одного и того же дерева.
algorithm Kruskal(G) is F:= ∅ for each v ∈ G.V do MAKE-SET(v) for each (u, v) in G.E ordered by weight(u, v), increasing do if FIND-SET(u) ≠ FIND-SET(v) then F:= F ∪ {(u, v)} ∪ {(v, u)} UNION(FIND-SET(u), FIND-SET(v)) return F
Сложность
Для графа с E ребрами и V вершинами можно показать, что алгоритм Крускала работает за время O ( E log E ) или, что эквивалентно, время O ( E log V ), и все это с простыми структурами данных. Эти времена работы эквивалентны, потому что:
- E - самое большее и .
- Каждая изолированная вершина является отдельным компонентом минимального остовного леса. Если мы игнорируем изолированные вершины, мы получаем V ≤ 2 E , поэтому log V равен .
Мы можем достичь этой границы следующим образом: сначала отсортируем ребра по весу, используя сортировку сравнения за время O ( E log E ); это позволяет шагу «удалить край с минимальным весом из S » работать с постоянным временем. Затем мы используем структуру данных с непересекающимися наборами, чтобы отслеживать, какие вершины находятся в каких компонентах. Мы помещаем каждую вершину в ее собственное непересекающееся множество, которое требует O ( V ) операций. Наконец, в худшем случае нам нужно перебрать все ребра, и для каждого ребра нам нужно выполнить две операции поиска и, возможно, одно объединение. Даже простая структура данных с непересекающимся множеством, такая как леса с непересекающимся множеством с объединением по рангу, может выполнять O ( E ) операций за время O ( E log V ). Таким образом, общее время O ( E log E ) = O ( E log V ).
При условии, что ребра либо уже отсортированы, либо могут быть отсортированы за линейное время (например, с помощью сортировки с подсчетом или сортировки по основанию ), алгоритм может использовать более сложную структуру данных с непересекающимися наборами для работы за время O ( E α ( V )). , где α - чрезвычайно медленно растущая обратная функция однозначной функции Аккермана .
Пример
Изображение | Описание |
---|---|
AD и CE - самые короткие ребра, их длина равна 5, а AD было выбрано произвольно , поэтому оно выделено. | |
CE теперь является самым коротким ребром, не образующим цикла, длиной 5, поэтому оно выделено как второе ребро. | |
Следующее ребро, DF длиной 6, выделяется почти таким же способом. | |
Следующие по длине ребра - это AB и BE , обе длины 7. AB выбирается произвольно и выделяется. Ребро BD было выделено красным, потому что уже существует путь (зеленый) между B и D , поэтому, если бы он был выбран , он образовал бы цикл ( ABD ). | |
Процесс продолжает выделять следующее наименьшее ребро, BE с длиной 7. На этом этапе красным цветом выделено гораздо больше ребер: BC, потому что он будет формировать цикл BCE , DE, потому что он будет формировать цикл DEBA , и FE, потому что он будет форма FEBAD . | |
Наконец, процесс заканчивается ребром EG длиной 9, и минимальное остовное дерево найдено. |
Доказательство правильности
Доказательство состоит из двух частей. Во-первых, доказывается, что алгоритм создает остовное дерево . Во-вторых, доказано, что построенное остовное дерево имеет минимальный вес.
Остовное дерево
Позвольте быть связным, взвешенным графом и пусть быть подграфом, созданным алгоритмом. не может иметь цикла, так как по определению ребро не добавляется, если оно приводит к циклу. не может быть отключен, так как первое встреченное ребро, которое соединяет два компонента, было бы добавлено алгоритмом. Таким образом, остовное дерево .
Минимальность
Мы показываем, что следующее предложение P истинно по индукции : если F - множество ребер, выбранных на любом этапе алгоритма, то существует некоторое минимальное остовное дерево, которое содержит F и ни одно из ребер не отклоняется алгоритмом.
- Ясно, что P истинно в начале, когда F пусто: подойдет любое минимальное остовное дерево, и оно существует, потому что взвешенный связный граф всегда имеет минимальное остовное дерево.
- Теперь предположит P верно для некоторых неконечного множества ребер F , и пусть T будет минимальным покрывающим деревом , которое содержит F .
- Если следующее выбранное ребро e также находится в T , то P истинно для F + e .
- В противном случае, если адрес не находится в Т , то Т + е имеет цикл C . Этот цикл содержит ребро , которые не принадлежат к F , так как е не образуют цикл , при добавлении к F , но делает в T . Пусть f - ребро, которое находится в C, но не в F + e . Обратите внимание, что f также принадлежит T , и P не учитывалась алгоритмом. Следовательно, f должен иметь вес не меньше e . Тогда Т - е + е представляет собой дерево, и оно имеет такой же или меньший вес , как и Т . Итак, T - f + e - это минимальное остовное дерево, содержащее F + e, и снова P выполняется.
- Следовательно, по принципу индукции P выполняется, когда F стало остовным деревом, что возможно только в том случае, если F само является минимальным остовным деревом.
Параллельный алгоритм
Алгоритм Крускала по своей сути является последовательным, и его трудно распараллелить. Однако можно выполнить начальную сортировку ребер параллельно или, в качестве альтернативы, использовать параллельную реализацию двоичной кучи для извлечения ребра с минимальным весом на каждой итерации. Поскольку на процессорах возможна параллельная сортировка по времени , время выполнения алгоритма Крускала можно сократить до O ( E α ( V )), где α снова является обратной по отношению к однозначной функции Аккермана .
Вариант алгоритма Краскала, названный Фильтр-Краскал, был описан Осиповым и др. и лучше подходит для распараллеливания. Основная идея Filter-Kruskal состоит в том, чтобы разделить ребра аналогично быстрой сортировке и отфильтровать ребра, которые соединяют вершины одного дерева, чтобы снизить стоимость сортировки. Следующий псевдокод демонстрирует это.
function filter_kruskal(G) is if |G.E| < kruskal_threshold: return kruskal(G) pivot = choose_random(G.E) , = partition(G.E, pivot) A = filter_kruskal() = filter() A = A ∪ filter_kruskal() return A function partition(E, pivot) is = ∅, = ∅ foreach (u, v) in E do if weight(u, v) <= pivot then = ∪ {(u, v)} else = ∪ {(u, v)} return , function filter(E) is = ∅ foreach (u, v) in E do if find_set(u) ≠ find_set(v) then = ∪ {(u, v)} return
Filter-Kruskal лучше подходит для распараллеливания, поскольку сортировку, фильтрацию и разбиение можно легко выполнять параллельно, распределяя границы между процессорами.
Наконец, были изучены другие варианты параллельной реализации алгоритма Крускала. Примеры включают схему, в которой используются вспомогательные потоки для удаления ребер, которые определенно не являются частью MST в фоновом режиме, и вариант, который запускает последовательный алгоритм на p подграфах, а затем объединяет эти подграфы до тех пор, пока не останется только один, последний MST.
Смотрите также
- Алгоритм Прима
- Алгоритм Дейкстры
- Алгоритм Борувки
- Алгоритм обратного удаления
- Односвязная кластеризация
- Жадный геометрический гаечный ключ
Рекомендации
- Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 23.2: Алгоритмы Краскала и Прима, стр. 567–574.
- Майкл Т. Гудрич и Роберто Тамассия . Структуры данных и алгоритмы в Java , четвертое издание. John Wiley & Sons, Inc., 2006. ISBN 0-471-73884-0 . Раздел 13.7.1: Алгоритм Крускала, стр. 632 ..