Алгоритм Прима — различия между версиями
Shagal (обсуждение | вклад) (→Пример работы алгоритма) |
Shagal (обсуждение | вклад) (→Пример работы алгоритма) |
||
Строка 39: | Строка 39: | ||
|style="background:#FFFF00"|<tex>\infty </tex> | |style="background:#FFFF00"|<tex>\infty </tex> | ||
|style="background:#FFFF00"|<tex>\infty </tex> | |style="background:#FFFF00"|<tex>\infty </tex> | ||
+ | |style="background:#f9f9f9"|p[] | ||
+ | |style="background:#f9f9f9"|<tex>-</tex> | ||
+ | |||
|- | |- | ||
|style="background:#f9f9f9"|key[] | |style="background:#f9f9f9"|key[] | ||
Строка 47: | Строка 50: | ||
|style="background:#FFFF00"|<tex>\infty </tex> | |style="background:#FFFF00"|<tex>\infty </tex> | ||
|style="background:#FFFF00"|<tex>\infty </tex> | |style="background:#FFFF00"|<tex>\infty </tex> | ||
+ | |style="background:#f9f9f9"|p[] | ||
+ | |style="background:#f9f9f9"|1 | ||
+ | |||
|- | |- | ||
|style="background:#f9f9f9"|key[] | |style="background:#f9f9f9"|key[] | ||
Строка 55: | Строка 61: | ||
|style="background:#FFFF00"|14 | |style="background:#FFFF00"|14 | ||
|style="background:#FFFF00"|<tex>\infty </tex> | |style="background:#FFFF00"|<tex>\infty </tex> | ||
+ | |style="background:#f9f9f9"|p[] | ||
+ | |style="background:#f9f9f9"|1 3 | ||
+ | |||
|- | |- | ||
|style="background:#f9f9f9"|key[] | |style="background:#f9f9f9"|key[] | ||
Строка 63: | Строка 72: | ||
|style="background:#FF0000"|14 | |style="background:#FF0000"|14 | ||
|style="background:#FFFF00"|71 | |style="background:#FFFF00"|71 | ||
+ | |style="background:#f9f9f9"|p[] | ||
+ | |style="background:#f9f9f9"|4 1 3 | ||
+ | |||
|- | |- | ||
|style="background:#f9f9f9"|key[] | |style="background:#f9f9f9"|key[] | ||
Строка 71: | Строка 83: | ||
|style="background:#FF0000"|14 | |style="background:#FF0000"|14 | ||
|style="background:#FFFF00"|71 | |style="background:#FFFF00"|71 | ||
+ | |style="background:#f9f9f9"|p[] | ||
+ | |style="background:#f9f9f9"|2 4 1 3 | ||
+ | |||
|- | |- | ||
|style="background:#f9f9f9"|key[] | |style="background:#f9f9f9"|key[] | ||
Строка 79: | Строка 94: | ||
|style="background:#FF0000"|14 | |style="background:#FF0000"|14 | ||
|style="background:#FF0000"|71 | |style="background:#FF0000"|71 | ||
+ | |style="background:#f9f9f9"|p[] | ||
+ | |style="background:#f9f9f9"|5 2 4 1 3 | ||
|} | |} | ||
Версия 09:04, 5 декабря 2011
Алгоритм Прима — алгоритм поиска минимального остовного дерева (minimum spanning tree, MST) во взвешенном неориентированном связном графе.
Содержание
Идея
Данный алгоритм очень похож на алгоритм Дейкстры. Будем последовательно строить поддерево ответа в графе , поддерживая приоритетную очередь из вершин , имеющую ключом для вершины (вес минимального ребра из вершин в вершину ). Также для каждой вершины очереди будем хранить — вершину , на которой достигается минимум в определении ключа. Дерево поддерживается неявно, и равно , где — корень . Изначально пусто, в очереди все вершины с ключами . Выберём произвольную вершину и присвоим её ключу . На каждом шаге будем извлекать минимальную вершину из приоритетной очереди и релаксировать все ребра , такие что , выполняя при этом и обновление . Ребро при этом добавляется к ответу.
Реализация
и
Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.
Пример работы алгоритма
1 | 2 | 3 | 4 | 5 | |||
key[] | p[] | ||||||
key[] | 0 | p[] | 1 | ||||
key[] | 0 | 7 | 14 | p[] | 1 3 | ||
key[] | 0 | 7 | 14 | 71 | p[] | 4 1 3 | |
key[] | 0 | 2 | 7 | 14 | 71 | p[] | 2 4 1 3 |
key[] | 0 | 2 | 7 | 14 | 71 | p[] | 5 2 4 1 3 |
Корректность
По поддерживаемым инвариантам после извлечения вершины лемме о безопасном ребре, оно безопасно. Алгоритм построения MST, добавляющий безопасные ребра, причём делающий это ровно раз, корректен.
( ) из ребро является ребром минимального веса, пересекающим разрез . Значит, поОценка производительности
Производительность алгоритма Прима зависит от выбранной реализации приоритетной очереди, как и в алгоритме Дейкстры. Извлечение минимума выполняется раз, релаксация — раз.
Структура данных для приоритетной очереди | Асимптотика времени работы |
---|---|
Наивная реализация | |
Двоичная куча | |
Куча Фибоначчи |
См. также
Литература
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — с.653 — 656.— ISBN 978-5-8459-0857-5 (рус.)