Главная » Java, Структуры данных и алгоритмы » Алгоритм Прима-Ярника

0

В алгоритме Прима-Ярника остовное дерево наименьшего размера произрастает из одного-единств^нного кластера, начинающегося из некоторого «корневого» узла v. Главная идея сходна с алгоритмом Дейкстры. Начиная с некоторого узла v, определяем начальное «окружение» узлов С. Затем при каждой итерации выбираем наименьший путь е = (v,w), соединяя узел v облака С с узлом и за его пределами. Узел и переносится в облако, и процесс повторяется до тех пор, пока остовное дерево не будет сформировано. Выбирая наименьший путь, соединяющий узел из С с узлом за пределами С, гарантируем соответствующее требованиям пути добавление узла в MST.

Для эффективной реализации этого подхода воспользуемся еще одной идеей алгоритма Дейкстры. Будем сохранять метку D[u] каждого узла и, не входящего в С, в которой находится вес наиболее подходящего на текущий момент для присоединения и к С пути. Эти метки должны обеспечить сокращение количества путей, которые необходимо обработать при определении узла, вводимого в облако.

Алгоритм PrimJarnik(G):

Input: взвешенный связный граф G из п узлов и т путей. Output: остовное дерево наименьшего размера Т для G.

Выбрать любой узел v в G D[v] <г- О

for каждого узла и * v do

D[v] <- +00 Инициировать Т <- 0.

Инициировать очередь с приоритетами О с объектом ((и, null), С[и]) для каждого узла и, где (и,null) является элементом, a D[u]) — ключом, while Q не является пустой do (и,е) <- Q.removeMin() Добавить узел и и путь ев Т.

for для каждого узла z, смежного с и, причем z находится в Q, do {выполнить восстановительную процедуру для (u,z)} if w({w,z)) < D[z] then D[z] <- w{{u,z))

Заменить элемент узла z в Q на (z, (u,z)) Заменить ключ узла zb Она D[z] return дерево T

Фрагмент кода 12.18. для решения MST-проблемы

Пусть пит обозначают соответственно количество узлов и путей в графе G. Принципы реализация алгоритма Прима-Ярника аналогичны принципам алгоритма Дейкстры. Если приоритетная очередь Q реализуется в виде стопки, поддерживающей локаторные методы приоритетной очереди (см. раздел 7.4), узел и при каждой итерации извлекается за 0(log п) времени, а значение D[z] обновляется тоже за 0(log п) времени, поскольку вычисления для каждого пути (u,z) будут выполняться максимум один раз. Последующие шаги в каждой итерации могут быть реализованы за пропорциональное 0(1) время. Таким образом, общее время выполнения составит 0((п + m)log п) времени, что равно 0(т log п). Следовательно, можно сделать следующий вывод.

Утверждение 12.20. Имея простой связный взвешенный граф G из п узлов и т путей, алгоритм Прима-Ярника строит остовное дерево наименьшего размера для G за 0(т log п) времени.

/

приводится на рис. 12.22 и 12.23. Сравнение алгоритмов решения MST-проблемы

Хотя описанные выше алгоритмы построения остовного дерева наименьшего размера имеют одинаковое время выполнения в наихудших ситуациях, каждый из них достигает результата по-своему.

Если говорить о дополнительных вспомогательных структурах, то алгоритм Крускала использует приоритетную очередь для хранения путей

и коллекцию множеств, реализованных списками, для хранения кластеров. использует только приоритетную очередь для хранения пар «узел-путь». Таким образом, с точки зрения удобства программирования алгоритм Прима-Ярника предпочтительнее. В принципе алгоритм Прима-Ярника настолько подобен алгоритму Дейкстры, что его реализация может быть легко получена из реализации последнего.

Рис. 12.22. (продолжение на рис. 12.23)

Рис. 12.23. (продолжение)

С точки же зрения постоянных факторов оба алгоритма достаточно схожи, так как время их выполнения зависит от относительного малого количества постоянных факторов.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии