Алгоритм Прима

Демонстрация алгоритма Прима, основанного на евклидовом расстоянии.

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

Алгоритм был разработан в 1930 году чешским математиком Войтехом Ярником. а затем заново открыт и переиздан учёным-компьютерщиком Робертом Примом в 1957 году. и Эдсгер В. Дейкстра в 1959 году. Поэтому его еще иногда называют алгоритмом Ярника , Алгоритм Прима–Ярника , Алгоритм Прима – Дейкстры или алгоритм DJP .

Другие известные алгоритмы решения этой задачи включают алгоритм Крускала и алгоритм Борувки . Эти алгоритмы находят минимальный остовный лес в возможно несвязном графе; Напротив, самая базовая форма алгоритма Прима находит только минимальные остовные деревья в связных графах. Однако, запуская алгоритм Прима отдельно для каждого связного компонента графа, его также можно использовать для поиска минимального остовного леса. С точки зрения асимптотической временной сложности эти три алгоритма одинаково быстры для разреженных графов , но медленнее, чем другие, более сложные алгоритмы. Однако для достаточно плотных графов алгоритм Прима можно заставить работать за линейное время , удовлетворяя или улучшая временные ограничения для других алгоритмов.

Алгоритм Прима, начинающийся с вершины A. На третьем этапе ребра BD и AB имеют вес 2, поэтому BD выбирается произвольно. После этого шага AB больше не является кандидатом на добавление в дерево, поскольку он связывает два узла, которые уже есть в дереве.

Описание

Алгоритм неформально можно описать как выполнение следующих шагов:

1. Инициализируйте дерево одной вершиной, произвольно выбранной из графа.
2. Вырастите дерево на одно ребро: из ребер, соединяющих дерево с вершинами, которых еще нет в дереве, найдите ребро с минимальным весом и перенесите его в дерево.
3. Повторяйте шаг 2 (пока все вершины не окажутся в дереве).

Более подробно это можно реализовать, следуя приведенному ниже псевдокоду .

1. Свяжите с каждой вершиной v графа число C [ v ] (самая дешевая стоимость соединения с v ) и ребро E [ v ] (ребро, обеспечивающее это самое дешевое соединение). Чтобы инициализировать эти значения, установите все значения C [ v ] на +∞ (или на любое число, превышающее максимальный вес ребра) и установите для каждого E [ v ] значение специального флага , указывающее, что нет ребра, соединяющего v с предыдущим. вершины.
2. Инициализировать пустой лес F и набор Q вершин, которые еще не включены в F (изначально все вершины).
3. Повторяйте следующие шаги, пока Q не станет пустым:
   1. Найдите и удалите вершину v из Q, имеющую минимально возможное значение C [ v ]
   2. Добавьте v к F
   3. Перебираем ребра vw, соединяя v с другими вершинами w . Для каждого такого ребра, если w по-прежнему принадлежит Q и vw имеет меньший вес, чем C [ w ], выполните следующие шаги:
      1. Установите C [ w ] на стоимость ребра vw
      2. Установите E [ w ] так, чтобы он указывал на ребро vw .
4. Возврат F , который включает в себя соответствующие ребра в E

Как описано выше, начальная вершина алгоритма будет выбрана произвольно, поскольку первая итерация основного цикла алгоритма будет иметь набор вершин из Q , все из которых имеют одинаковый вес, и алгоритм автоматически запустит новое дерево в F , когда он завершает связующее дерево каждого связного компонента входного графа. Алгоритм можно изменить так, чтобы он начинался с любой конкретной вершины s, задав C [ s ] числом, меньшим, чем другие значения C (например, ноль), и его можно модифицировать так, чтобы он находил только одно связующее дерево, а не весь охватывающий лес (более точно соответствующий неформальному описанию), останавливаясь всякий раз, когда он встречает другую вершину, помеченную как не имеющую связанного ребра.

Различные варианты алгоритма отличаются друг от друга тем, как множество Q реализовано : в виде простого связного списка или массива вершин или в виде более сложной структуры данных очереди приоритетов . Такой выбор приводит к различиям во временной сложности алгоритма. В общем, приоритетная очередь будет быстрее находить вершину v с минимальными затратами, но повлечет за собой более дорогие обновления при изменении значения C [ w ].

Временная сложность

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

Временная сложность алгоритма Прима зависит от структур данных, используемых для графа, и от упорядочивания ребер по весу, что можно сделать с помощью очереди с приоритетами . В следующей таблице показаны типичные варианты:

Структура данных с минимальным весом ребра	Временная сложность (общая)
матрица смежности , поиск	$O(|V|^{2})$
двоичная куча и список смежности	$O((|V|+|E|)\log |V|)=O(|E|\log |V|)$
Куча Фибоначчи и список смежности	$O(|E|+|V|\log |V|)$

Простая реализация Prim, использующая матрицу смежности или графическое представление списка смежности и линейный поиск в массиве весов, чтобы найти ребро минимального веса для добавления, требует O (|V| ² ) время работы. Однако это время работы можно значительно сократить, используя кучи для реализации поиска ребер минимального веса во внутреннем цикле алгоритма.

Первая улучшенная версия использует кучу для хранения всех ребер входного графа, упорядоченных по их весу. Это приводит к времени работы в худшем случае O(|E| log |E|). Но сохранение вершин вместо ребер может еще больше улучшить ситуацию. Куча должна упорядочивать вершины по наименьшему весу ребра, который соединяет их с любой вершиной частично построенного минимального остовного дерева (MST) (или бесконечности, если такого ребра не существует). Каждый раз, когда вершина v выбирается и добавляется в MST, операция уменьшения ключа выполняется для всех вершин w за пределами частичного MST, так что v соединяется с w , устанавливая ключ на минимум его предыдущего значения и стоимости ребра. из ( v , w ).

Используя простую структуру данных двоичной кучи , теперь можно показать, что алгоритм Прима работает за время O (|E| log |V|), где |E| — количество ребер, а |V| это количество вершин. Используя более сложную кучу Фибоначчи , это можно свести к O (|E| + |V| log |V|), что асимптотически быстрее , если граф достаточно плотный , чтобы |E| есть ω (|V|), а линейное время , когда |E| не ниже |V| журнал |В|. Для графов еще большей плотности (имеющих не менее |V| ^с ребра для некоторого c > 1), алгоритм Прима можно заставить работать за линейное время еще проще, используя d -арную кучу вместо кучи Фибоначчи.

Демонстрация доказательств. В этом случае граф Y ₁ = Y − f + e уже равен Y . В общем, процесс, возможно, придется повторить.

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

Пусть P — связный взвешенный граф . На каждой итерации алгоритма Прима должно быть найдено ребро, соединяющее вершину подграфа с вершиной вне подграфа. Поскольку P связен, к каждой вершине всегда будет путь. Выход Y алгоритма Прима представляет собой дерево , поскольку ребро и вершина, добавленные в дерево Y, связаны. Пусть Y ₁ — минимальное остовное дерево графа P. Если Y ₁ = Y , то Y — минимальное остовное дерево. В противном случае пусть e — первое ребро, добавленное при построении дерева Y , которого нет в дереве Y ₁ , а V — множество вершин, соединенных ребрами, добавленными перед ребром e . Тогда один конец ребра e находится в множестве V , а другой — нет. Поскольку дерево Y ₁ является остовным деревом графа P существует путь, , в дереве Y ₁ соединяющий две конечные точки. Двигаясь по пути, он должен встретить ребро f, вершину из множества V с вершиной, которой нет в множестве V. соединяющее Теперь на итерации, когда ребро e было добавлено к дереву Y , ребро f также могло быть добавлено, и оно было бы добавлено вместо ребра. e, если его вес был меньше e , и поскольку ребро f не добавлялось, заключаем, что

$w(f)\geq w(e).$

Пусть дерево Y ₂ — граф, полученный удалением ребра f и добавлением ребра e из дерева Y ₁ к нему . Легко показать, что дерево Y ₂ связно, имеет то же количество ребер, что и дерево Y ₁ , а общий вес его ребер не больше, чем у дерева Y ₁ , поэтому оно также является минимальным остовным деревом графа P и содержит ребро e добавленные до него при построении множества V. и все ребра , описанные выше, и в конечном итоге мы получим минимальное остовное дерево графа P , идентичное дереву Y. Повторите шаги , Это показывает, что Y — минимальное остовное дерево. Минимальное связующее дерево позволяет расширить первое подмножество субрегиона до большего подмножества X , которое мы считаем минимальным.

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

Матрица смежности распределена между несколькими процессорами для параллельного алгоритма Прима. На каждой итерации алгоритма каждый процессор обновляет свою часть C , проверяя строку вновь вставленной вершины в своем наборе столбцов в матрице смежности. Затем результаты собираются, и следующая вершина для включения в MST выбирается глобально.

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

1. Назначьте каждый процессор $P_{i}$ набор $V_{i}$ последовательных вершин длины ${\tfrac {|V|}{|P|}}$.
2. Создайте C, E, F и Q, как в последовательном алгоритме , и разделите C, E, а также граф между всеми процессорами так, чтобы каждый процессор удерживал входящие ребра в свой набор вершин. Позволять $C_{i}$, $E_{i}$ обозначают части C , E, хранящиеся в процессоре $P_{i}$.
3. Повторяйте следующие шаги, пока Q не станет пустым:
   1. На каждом процессоре: найдите вершину $v_{i}$ имеющий минимальное значение в $C_{i}$[ $v_{i}$] (локальное решение).
   2. Минимизируйте локальные решения, чтобы найти вершину v , имеющую минимально возможное значение C [ v ] (глобальное решение).
   3. Трансляция выбранного узла на каждый процессор.
   4. Добавьте v к F и, если E [ v ] не является значением специального флага, также добавьте E [ v ] к F .
   5. На каждом процессоре: обновить $C_{i}$ и $E_{i}$ как в последовательном алгоритме.
4. Возврат Ф

Этот алгоритм обычно может быть реализован на распределенных машинах. а также на машинах с общей памятью. Время работы $O({\tfrac {|V|^{2}}{|P|}})+O(|V|\log |P|)$, предполагая, что операции сокращения и трансляции могут выполняться в $O(\log |P|)$. Также был исследован вариант алгоритма Прима для машин с общей памятью, в котором последовательный алгоритм Прима выполняется параллельно, начиная с разных вершин. Однако следует отметить, что существуют более сложные алгоритмы для распределенного минимального остовного дерева более эффективного решения проблемы .

См. также

• Алгоритм Дейкстры , очень похожий алгоритм решения задачи о кратчайшем пути.
• Гридоиды предлагают общий способ понять правильность алгоритма Прима.

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

• Алгоритм Прима прогрессирует в случайно распределенных точках
• СМИ, связанные с алгоритмом Прима, на Викискладе?