Алгоритм Прима — различия между версиями
Shagal (обсуждение | вклад) (→Пример работы алгоритма) |
|||
Строка 118: | Строка 118: | ||
== См. также == | == См. также == | ||
* [[Алгоритм Краскала]] | * [[Алгоритм Краскала]] | ||
− | + | == Визуализация алгоритма == | |
+ | [http://www.mincel.com/java/prim.html Алгоритм Прима] | ||
== Литература == | == Литература == | ||
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — с.653 — 656.— ISBN 978-5-8459-0857-5 (рус.) | * ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — с.653 — 656.— ISBN 978-5-8459-0857-5 (рус.) |
Версия 23:10, 31 декабря 2011
Алгоритм Прима — алгоритм поиска минимального остовного дерева (minimum spanning tree, MST) во взвешенном неориентированном связном графе.
Содержание
Идея
Данный алгоритм очень похож на алгоритм Дейкстры. Будем последовательно строить поддерево ответа в графе , поддерживая приоритетную очередь из вершин , имеющую ключом для вершины величину (вес минимального ребра из вершин в вершину ). Также для каждой вершины очереди будем хранить — вершину , на которой достигается минимум в определении ключа. Дерево поддерживается неявно, и его ребра — это пары , где , а — корень . Изначально пусто, в очереди все вершины с ключами . Выберём произвольную вершину и присвоим её ключу . На каждом шаге будем извлекать минимальную вершину из приоритетной очереди и релаксировать все ребра , такие что , выполняя при этом операцию над очередью и обновление . Ребро при этом добавляется к ответу.
Реализация
произвольная вершина в и
Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.
Корректность
По поддерживаемым инвариантам после извлечения вершины лемме о безопасном ребре, оно безопасно. Алгоритм построения MST, добавляющий безопасные ребра, причём делающий это ровно раз, корректен.
( ) из ребро является ребром минимального веса, пересекающим разрез . Значит, поОценка производительности
Производительность алгоритма Прима зависит от выбранной реализации приоритетной очереди, как и в алгоритме Дейкстры. Извлечение минимума выполняется раз, релаксация — раз.
Структура данных для приоритетной очереди | Асимптотика времени работы |
---|---|
Наивная реализация | |
Двоичная куча | |
Куча Фибоначчи |
Пример работы алгоритма
№ шага | состояние | граф |
1) Получаем на вход граф, все вершины находятся в куче, ключи всех вершин | .key[] : [ Q : [1, 2, 3, 4, 5] вершина с минимальным ключом : p[] : edges[] : |
, , , , ]
|
2) Выбрали первую вершину пути(1). Поменяли ключ стартовой вершины на 0. Убрали ее из кучи, так как ее ключ минимален. | key[] : [ Q : [2, 3, 4, 5] вершина с минимальным ключом : ключ 0p[] : [1] edges[]: |
, , , , ]
|
3) Смотрим на детей вершины (1). Расставляем им ключи. Находим в куче вершину с минимальным ключом(3). Удаляем ее из кучи, добавляем в ответ. | key[] : [0, Q : [2, 4, 5] вершина с минимальным ключом : 3 с ключом 7 p[] : [1, 3] edges: [(1, 3)] |
, 7, 14, ]
|
4)Смотрим на детей вершины (3). Расставляем им ключи. Находим в куче вершину с минимальным ключом(2).Удаляем ее из кучи, добавляем в ответ. | key[] : [0, Q : [2, 5] вершина с минимальным ключом : 4 с ключом 14 p[] : [1, 3, 4] edges: [(1, 3), (4, 1)] |
, 7, 14, 71]
|
5)Смотрим на детей вершины (4). Расставляем им ключи. Находим в куче вершину с минимальным ключом(2).Удаляем ее из кучи, добавляем в ответ. | key[] : [0, 4, 7, 14, 71]
Q :[5] вершина с минимальным ключом : 2 с ключом 4 p[] : [1, 3, 4, 2] edges: [(1, 3), (4, 1), (4, 2)] |
|
6)Смотрим на детей вершины (2). Расставляем им ключи. Находим в куче вершину с минимальным ключом(5).Удаляем ее из кучи, добавляем в ответ. | key[] : [0, 4, 7, 14, 52]
Q :[] вершина с минимальным ключом : 5 с ключом 52 p[] : [1, 3, 4, 2, 5] edges: [(1, 3), (4, 1), (4, 2), (2, 5)] |
См. также
Визуализация алгоритма
Литература
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — с.653 — 656.— ISBN 978-5-8459-0857-5 (рус.)