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

Алгоритм Крускала ^[1] находит минимальный остовной лес неориентированного графа с рёберным весом . Если граф связный , он находит минимальное остовное дерево . Это жадный алгоритм , который на каждом шаге добавляет к лесу ребро с наименьшим весом, которое не образует цикл . ^[2] Ключевыми шагами алгоритма являются сортировка и использование структуры данных непересекающегося множества для обнаружения циклов. Время его работы определяется временем сортировки всех рёбер графа по их весу.

Минимальное остовное дерево связного взвешенного графа — это связный подграф без циклов, для которого сумма весов всех ребер в подграфе минимальна. Для несвязного графа минимальный остовный лес состоит из минимального остовного дерева для каждого связного компонента .

Этот алгоритм был впервые опубликован Джозефом Крускалом в 1956 году ^[3] и вскоре после этого был переоткрыт Лоберманом и Вайнбергером (1957). ^[4] Другие алгоритмы для этой задачи включают алгоритм Прима , алгоритм Борувки и алгоритм обратного удаления .

Алгоритм

Алгоритм выполняет следующие шаги:

Создайте лес (набор деревьев), изначально состоящий из отдельного одновершинного дерева для каждой вершины входного графа.
Отсортируйте ребра графа по весу.
Пройтись по ребрам графа в порядке возрастания их веса. Для каждого ребра:
- Проверьте, приведет ли добавление ребра к текущему лесу к созданию цикла.
- Если нет, добавьте опушку к лесу, объединив два дерева в одно.

По завершении алгоритма лес образует минимальный остовной лес графа. Если граф связный, лес имеет один компонент и образует минимальное остовное дерево.

Псевдокод

Следующий код реализован с использованием структуры данных непересекающегося множества . Он представляет лес F как набор ненаправленных ребер и использует структуру данных непересекающегося множества для эффективного определения того, являются ли две вершины частью одного и того же дерева.

Алгоритм Крускала ( G ) — это Ф:= ∅ для каждого v в GV сделать СДЕЛАТЬ-SET(v) для каждого {u, v} в GE, упорядоченном по весу ({u, v}), увеличивая do  если FIND-SET(u) ≠ FIND-SET(v) тогда Ф := Ф ∪ { {u, v} } ОБЪЕДИНЕНИЕ(НАЙТИ-НАБОР(u), НАЙТИ-НАБОР(v)) возвращение F

Сложность

Для графа с $E$ ребрами и $V$ вершинами можно показать, что алгоритм Краскала работает за время $O (E log E)$ с простыми структурами данных. Здесь $O$ выражает время в большой нотации O , а $log$ является логарифмом по любому основанию (поскольку внутри $O$ -нотации логарифмы по всем основаниям эквивалентны, потому что они одинаковы с точностью до постоянного множителя). Это ограничение по времени часто записывается как $O (E log V)$ , что эквивалентно для графов без изолированных вершин, потому что для этих графов $V /2 \leq E < V 2$ и логарифмы $V$ и $E$ снова находятся в пределах постоянного множителя друг от друга.

Чтобы достичь этой границы, сначала отсортируйте ребра по весу, используя сортировку сравнением за время $O (E log E)$ . После сортировки можно выполнить цикл по ребрам в отсортированном порядке за постоянное время на ребро. Затем используйте структуру данных непересекающегося множества с набором вершин для каждого компонента, чтобы отслеживать, какие вершины находятся в каких компонентах. Создание этой структуры с отдельным набором для каждой вершины занимает $V$ операций и $O (V)$ времени. Окончательная итерация по всем ребрам выполняет две операции поиска и, возможно, одну операцию объединения на ребро. Эти операции занимают амортизированное время $O (α (V))$ на операцию, что дает наихудшее общее время $O (E α (V))$ для этого цикла, где $α$ — чрезвычайно медленно растущая обратная функция Аккермана . Эта часть временной границы намного меньше времени для шага сортировки, поэтому общее время для алгоритма можно упростить до времени для шага сортировки.

В случаях, когда ребра уже отсортированы или имеют достаточно малый целочисленный вес, позволяющий алгоритмам целочисленной сортировки, таким как сортировка подсчетом или радиксная сортировка, сортировать их за линейное время, операции с непересекающимися множествами являются самой медленной оставшейся частью алгоритма, а общее время составляет $O (E α(V))$ .

Пример

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

Доказательство состоит из двух частей. Во-первых, доказывается, что алгоритм создает остовное дерево . Во-вторых, доказывается, что построенное остовное дерево имеет минимальный вес.

Связующее дерево

Пусть будет связным, взвешенным графом и пусть будет подграфом , созданным алгоритмом. не может иметь цикл, так как по определению ребро не добавляется, если оно приводит к циклу. не может быть отсоединен, так как первое встреченное ребро, соединяющее два компонента , было бы добавлено алгоритмом. Таким образом, является остовным деревом . $G$ $Y$ $G$ $Y$ $Y$ $Y$ $Y$ $G$

Минимальность

Покажем, что следующее предложение P истинно по индукции : если F — множество ребер, выбранных на любом этапе алгоритма, то существует некоторое минимальное остовное дерево, содержащее F и ни одно из ребер, отклоненных алгоритмом.

Очевидно, что P истинно в начале, когда F пусто: подойдет любое минимальное остовное дерево, и оно существует, поскольку взвешенный связный граф всегда имеет минимальное остовное дерево.
Теперь предположим, что P истинно для некоторого неконечного множества ребер F , и пусть T — минимальное остовное дерево, содержащее F.
- Если следующее выбранное ребро e также принадлежит T , то P истинно для F + e .
- В противном случае, если e не принадлежит T, то T + e имеет цикл C. Цикл C содержит ребра, которые не принадлежат F + e , так как e не образует цикл при добавлении к F, но образует его в T. Пусть f будет ребром, которое принадлежит C , но не принадлежит F + e . Обратите внимание, что f также принадлежит T , так как f принадлежит T + e , но не принадлежит F + e . По P , f не рассматривался алгоритмом. Следовательно, f должен иметь вес, по крайней мере, такой же большой, как e . Тогда T − f + e является деревом, и оно имеет такой же или меньший вес, что и T. Однако, поскольку T является минимальным остовным деревом, то T − f + e имеет тот же вес, что и T , в противном случае мы получаем противоречие, и T не будет минимальным остовным деревом. Таким образом, T − f + e является минимальным остовным деревом, содержащим F + e, и снова выполняется P.
Следовательно, по принципу индукции, P выполняется, когда F становится остовным деревом, что возможно только в том случае, если F само является минимальным остовным деревом.

Параллельный алгоритм

Алгоритм Крускала по своей сути последовательный и его трудно распараллелить. Однако возможно выполнить начальную сортировку ребер параллельно или, в качестве альтернативы, использовать параллельную реализацию двоичной кучи для извлечения ребра с минимальным весом в каждой итерации. ^[5] Поскольку параллельная сортировка возможна по времени на процессорах, ^[6] время выполнения алгоритма Крускала можно сократить до O ( E α( V )), где α снова является обратной функцией однозначной функции Аккермана . $O(n)$ $O(\log n)$

Вариант алгоритма Крускала, названный Filter-Kruskal, был описан Осиповым и др. ^[7] и лучше подходит для распараллеливания. Основная идея Filter-Kruskal заключается в разбиении ребер аналогично быстрой сортировке и отфильтровывании ребер, которые соединяют вершины одного дерева, чтобы снизить стоимость сортировки. Следующий псевдокод демонстрирует это.

функция filter_kruskal(G) если | GE| < kruskal_threshold: возвращает kruskal(G) ось = выбрать_случайный(GE) E _≤ , E _> = раздел(GE, pivot) A = фильтр_крускал(E _≤ ) E _> = фильтр(E _> ) A = A ∪ filter_kruskal(E _> ) вернуть Aфункция partition(E, pivot) равна E _≤ = ∅, E _> = ∅ foreach (u, v) in E do  if weight(u, v) ≤ pivot then E _≤ = E _≤ ∪ {(u, v)} else E _> = E _> ∪ {(u, v)} return E _≤ , E _>функция filter(E) равна E _f = ∅ foreach (u, v) in E do  if find_set(u) ≠ find_set(v) then E _f = E _f ∪ {(u, v)} return E _f

Фильтр-Крускал лучше поддается распараллеливанию, поскольку сортировка, фильтрация и разбиение могут легко выполняться параллельно путем распределения ребер между процессорами. ^[7]

Наконец, были исследованы другие варианты параллельной реализации алгоритма Крускала. Примеры включают схему, которая использует вспомогательные потоки для удаления ребер, которые определенно не являются частью MST в фоновом режиме, ^[8] и вариант, который запускает последовательный алгоритм на p подграфах, а затем объединяет эти подграфы, пока не останется только один, финальный MST. ^[9]

Смотрите также

Ссылки

^ Кляйнберг, Джон (2006). Алгоритм проектирования. Ева Тардос. Бостон: Пирсон/Аддисон-Уэсли. стр. 142–151. ISBN 0-321-29535-8. OCLC 57422612.
^ Кормен, Томас; Чарльз Э. Лейзерсон, Рональд Л. Ривест, Клиффорд Стейн (2009). Введение в алгоритмы (Третье изд.). МТИ Пресс. стр. 631. ISBN. 978-0262258104.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Kruskal, JB (1956). «О кратчайшем остовном поддереве графа и задаче коммивояжера». Труды Американского математического общества . 7 (1): 48–50. doi : 10.1090/S0002-9939-1956-0078686-7 . JSTOR 2033241.
^ Лоберман, Х.; Вайнбергер, А. (октябрь 1957 г.). «Формальные процедуры для соединения клемм с минимальной общей длиной провода». Журнал ACM . 4 (4): 428–437. doi : 10.1145/320893.320896 . S2CID 7320964.
^ Куинн, Майкл Дж.; Део, Нарсингх (1984). «Алгоритмы на параллельных графах». Обзоры вычислительной техники ACM . 16 (3): 319–348. дои : 10.1145/2514.2515 . S2CID 6833839.
^ Грама, Анант; Гупта, Аншул; Карипис, Георгий; Кумар, Випин (2003). Введение в параллельные вычисления . Аддисон-Уэсли. стр. 412–413. ISBN 978-0201648652.
^ ab Осипов, Виталий; Сандерс, Питер; Синглер, Йоханнес (2009). "Алгоритм минимального остовного дерева фильтра-краскала". Труды одиннадцатого семинара по разработке алгоритмов и экспериментам (ALENEX). Общество промышленной и прикладной математики : 52–61. doi : 10.1137/1.9781611972894.5 . ISBN 978-0-89871-930-7.
^ Кацигианнис, Анастасиос; Анастопулос, Никос; Константинос, Никас; Козирис, Нектарий (2012). «Подход к распараллеливанию алгоритма Краскала с использованием вспомогательных потоков». 26-й Международный симпозиум IEEE по параллельной и распределенной обработке, 2012 г., семинары и докторский форум (PDF) . стр. 1601–1610. дои : 10.1109/IPDPSW.2012.201. ISBN 978-1-4673-0974-5. S2CID 14430930.
^ Лончар, Владимир; Шкрбич, Срджан; Балаж, Антун (2014). «Распараллеливание алгоритмов минимального остовного дерева с использованием архитектур с распределенной памятью». Труды по инженерным технологиям . С. 543–554. doi :10.1007/978-94-017-8832-8_39. ISBN 978-94-017-8831-1.

Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стайн . Введение в алгоритмы , второе издание. 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..

Внешние ссылки

Данные для примера статьи.
Плагин Gephi для расчета исходного кода минимального остовного дерева.
Алгоритм Крускала с примером и программой на языке C++
Код алгоритма Крускала на языке C++ применительно к случайным числам
Код алгоритма Крускала на Python с пояснениями