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

Алгоритм минимального остовного леса, который жадно добавляет ребра

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

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

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

Алгоритм

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

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

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

Псевдокод

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

алгоритм Крускала ( G ) Ф:= ∅ для каждого v в GV сделайте MAKE-SET(v) для каждого {u, v} в GE, упорядоченного по весу ({u, v}), увеличивая do  , если FIND-SET(u) ≠ FIND-SET(v), то F := F ∪ { {u, v} } СОЮЗ(НАЙТИ-НАБОР(u), НАЙТИ-НАБОР(v)) вернуть F

Сложность

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

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

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

Пример

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

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

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

Пусть это связный взвешенный граф и пусть это подграф, созданный алгоритмом. не может иметь цикл, поскольку по определению ребро не добавляется, если оно приводит к образованию цикла. не может быть отключен, так как первое встреченное ребро, соединяющее два компонента, было бы добавлено алгоритмом. Таким образом, является связующим деревом . ${\displaystyle G}$ ${\displaystyle Y}$ ${\displaystyle G}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle 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 )), где α снова является обратной однозначной функцией Аккермана . ${\displaystyle O(n)}$ ${\displaystyle O(\log n)}$

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

функция filter_kruskal(G) — это  if |GE| < kruskal_threshold: return kruskal(G) точка поворота = select_random(GE) E ≤ , E > = раздел (GE, точка поворота) A = filter_kruskal(E ≤ ) E > = фильтр (E > ) A = A ∪ filter_kruskal(E > ) return Aфункция part(E, Pivot) равна E ≤ = ∅, E > = ∅ foreach (u, v) в E do  , если вес (u, v) ≤ Pivot , то E ≤ = E ≤ ∪ {(u, v)} else E > = E > ∪ {(u, v)} return E ≤ , E >функция filter(E) равна E f = ∅ foreach (u, v) в E do  , если find_set(u) ≠ find_set(v) , то E f = E f ∪ {(u, v)} return E f

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

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

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

• Алгоритм Прима
• Алгоритм Дейкстры
• Алгоритм Борувки
• Алгоритм обратного удаления
• Кластеризация с одной связью
• Жадный геометрический гаечный ключ

Рекомендации

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