Алгоритм Краскала - Википедия - Kruskals algorithm

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

Этот алгоритм впервые появился в Труды Американского математического общества, pp. 48–50 в 1956 г., и был написан Джозеф Крускал.[2]

Другие алгоритмы решения этой проблемы включают Алгоритм Прима, то алгоритм обратного удаления, и Алгоритм Борувки.

Алгоритм

  • создать лес F (набор деревьев), где каждая вершина в графе является отдельным дерево
  • создать набор S содержащий все ребра в графе
  • пока S является непустой и F еще нет охватывающий
    • удалить край с минимальным весом из S
    • если удаленное ребро соединяет два разных дерева, добавьте его в лес F, объединяя два дерева в одно дерево

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

Псевдокод

Демонстрация алгоритма Крускала на полный график с весами на основе евклидова расстояния.

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

алгоритм Крускал (грамм) является    F: = ∅ для каждого v ∈ G.V делать        СОЗДАТЬ-НАБОР (v) для каждого (u, v) в G.E упорядочен по весу (u, v), увеличиваясь делать        если НАЙТИ-НАБОР (u) ≠ НАЙТИ-НАБОР (v) тогда            F: = F ∪ {(u, v)} UNION (FIND-SET (u), FIND-SET (v)) возвращаться F

Сложность

Для графика с E края и V вершин, можно показать, что алгоритм Крускала работает в О (E бревно E) время или, что то же самое, О(E бревно V) время, и все это с простыми структурами данных. Эти времена работы эквивалентны, потому что:

  • E самое большее и .
  • Каждая изолированная вершина является отдельным компонентом минимального остовного леса. Если игнорировать изолированные вершины, получим V ≤ 2E, так что журнал V является .

Мы можем достичь этой границы следующим образом: сначала отсортируем ребра по весу, используя сортировка сравнения в О(E бревно E) время; это позволяет ступеньке "удалить край с минимальным весом из S"работать в постоянное время. Далее мы используем непересекающаяся структура данных чтобы отслеживать, какие вершины находятся в каких компонентах. Помещаем каждую вершину в ее собственное непересекающееся множество, которое занимает O (V) операции. Наконец, в худшем случае нам нужно перебрать все ребра, и для каждого ребра нам нужно выполнить две операции поиска и, возможно, одно объединение. Даже простая структура данных с непересекающимся множеством, такая как леса с непересекающимся множеством с объединением по рангу, может выполнить O (E) операции в О(E бревно V) время. Таким образом, общее время О(E бревно E) = О(E бревно V).

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

Пример

ИзображениеОписание
Алгоритм Краскала 1.svgОБЪЯВЛЕНИЕ и CE - самые короткие ребра длиной 5, а ОБЪЯВЛЕНИЕ был произвольно выбрано, поэтому оно выделено.
Алгоритм Краскала 2.svgCE теперь самое короткое ребро, не образующее цикла, длиной 5, поэтому оно выделяется как второе ребро.
Алгоритм Краскала 3.svgСледующий край, DF длиной 6 выделяется почти таким же способом.
Алгоритм Краскала 4.svgСледующие по длине ребра - это AB и БЫТЬ, обе длиной 7. AB выбирается произвольно и выделяется. Край BD был выделен красным, потому что уже существует путь (зеленый) между B и D, поэтому он будет образовывать цикл (ABD) если бы он был выбран.
Алгоритм Краскала 5.svgПроцесс продолжает выделять следующий самый маленький край, БЫТЬ длиной 7. На этом этапе красным выделено еще много ребер: до н.э потому что это образует петлю До н.э., DE потому что это образует петлю DEBA, и FE потому что это сформирует FEBAD.
Алгоритм Краскала 6.svgНаконец, процесс заканчивается кромкой НАПРИМЕР длины 9, и найдено минимальное остовное дерево.

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

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

Остовное дерево

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

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

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

  • Четко п верно вначале, когда F пусто: подойдет любое минимальное остовное дерево, и оно существует, потому что взвешенный связный граф всегда имеет минимальное остовное дерево.
  • Теперь предположим п верно для некоторого неокончательного набора ребер F и разреши Т быть минимальным остовным деревом, содержащим F.
    • Если следующее выбранное ребро е также в Т, тогда п верно для F + е.
    • В противном случае, если е не в Т тогда Т + е имеет цикл C. Этот цикл содержит ребра, не принадлежащие F, поскольку е не образует цикла при добавлении к F но делает в Т. Позволять ж быть гранью, которая находится в C но не в F + е. Обратите внимание, что ж также принадлежит Т, и по п не учтено алгоритмом. ж поэтому должен иметь вес не менее е. потом Тж + е дерево, и оно имеет такой же или меньший вес, как Т. Так Тж + е минимальное остовное дерево, содержащее F + е и опять п держит.
  • Следовательно, по принципу индукции п держится, когда F стал остовным деревом, что возможно, только если F является минимальным остовным деревом.

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

Алгоритм Крускала по своей сути последователен и его трудно распараллелить. Однако возможно выполнить начальную сортировку ребер параллельно или, в качестве альтернативы, использовать параллельную реализацию двоичная куча для извлечения ребра минимального веса на каждой итерации.[3]Возможна параллельная сортировка по времени на процессоры,[4] время выполнения алгоритма Крускала можно сократить до О(E α (V)), где α снова обратное к однозначной Функция Аккермана.

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

функция filter_kruskal (G) является    если | G.E | <порог краскала: возвращаться краскал (G) pivot = choose_random (G.E) ,  = раздел (G.E, pivot) A = filter_kruskal ()     = фильтр () A = A ∪ filter_kruskal ()    возвращаться Афункция раздел (E, стержень) является     = ∅,  = ∅    для каждого (u, v) в E делать        если вес (u, v) <= pivot тогда             =  ∪ {(u, v)} еще             =  ∪ {(u, v)} возвращаться , функция фильтр (E) является     = ∅    для каждого (u, v) в E делать        если find_set (u) ≠ find_set (v) тогда             =  ∪ {(u, v)} возвращаться 

Filter-Kruskal лучше подходит для распараллеливания, поскольку сортировку, фильтрацию и разделение можно легко выполнять параллельно, распределяя грани между процессорами.[5]

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

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

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

  1. ^ Кормен, Томас; Чарльз Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн (2009). Введение в алгоритмы (Третье изд.). MIT Press. стр.631. ISBN  978-0262258104.CS1 maint: несколько имен: список авторов (связь)
  2. ^ Крускал, Дж. Б. (1956). «О кратчайшем остовном поддереве графа и задаче коммивояжера». Труды Американского математического общества. 7 (1): 48–50. Дои:10.1090 / S0002-9939-1956-0078686-7. JSTOR  2033241.
  3. ^ Куинн, Майкл Дж .; Део, Нарсинг (1984). «Алгоритмы параллельных графов». Опросы ACM Computing. 16 (3): 319–348. Дои:10.1145/2514.2515.
  4. ^ Грама, Анант; Гупта, Аншул; Карипис, Джордж; Кумар, Випин (2003). Введение в параллельные вычисления. С. 412–413. ISBN  978-0201648652.
  5. ^ а б Осипов, Виталий; Сандерс, Питер; Синглер, Йоханнес (2009). "Алгоритм минимального остовного дерева фильтр-Краскала" (PDF). Труды одиннадцатого семинара по разработке алгоритмов и экспериментов (ALENEX). Общество промышленной и прикладной математики: 52–61.
  6. ^ Кацигианнис, Анастасиос; Анастопулос, Никос; Константинос, Никас; Козирис, Нектариос (2012). «Подход к распараллеливанию алгоритма Краскала с использованием вспомогательных потоков» (PDF). Семинары симпозиума параллельной и распределенной обработки и форум PHD (IPDPSW), 2012 IEEE 26th International: 1601–1610.
  7. ^ Лончар, Владимир; Шкрбич, Срджан; Балаж, Антун (2014). «Распараллеливание алгоритмов минимального связующего дерева с использованием архитектур с распределенной памятью». Сделки по инженерным технологиям.: 543–554.

внешняя ссылка