Алгоритм Краскала - 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 самое большее ${\displaystyle V^{2}}$ и ${\displaystyle \log V^{2}=2\log V\in O(\log V)}$.
• Каждая изолированная вершина является отдельным компонентом минимального остовного леса. Если игнорировать изолированные вершины, получим V ≤ 2E, так что журнал V является ${\displaystyle O(\log E)}$.

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Кормен, Томас; Чарльз Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн (2009). Введение в алгоритмы (Третье изд.). MIT Press. стр.631. ISBN  978-0262258104.
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.

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