Алгоритм Прима — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример работы алгоритма)
Строка 41: Строка 41:
 
|}
 
|}
  
 
==Пример работы алгоритма==
 
 
{| border="1" cellpadding="3" cellspacing="0" style="text-align:center" width=70%
 
|-
 
|rowspan="1"|№ шага
 
|состояние
 
|граф
 
|-
 
|style="background:#f9f9f9" width="30%"|1) Получаем на вход граф, все вершины находятся в куче, ключи  всех вершин <tex>inf</tex>.
 
|width="150%"|key[] : [<tex>inf</tex>, <tex>inf</tex>, <tex>inf</tex>, <tex>inf</tex>, <tex>inf</tex>]
 
Q : [1, 2, 3, 4, 5]
 
 
вершина с минимальным ключом : <tex>-</tex>
 
 
p[] : <tex>-</tex>
 
 
edges[] : <tex>-</tex>
 
|[[Файл:Prim20.jpg|center|300px]]
 
|-
 
|style="background:#f9f9f9" width="30%"|2) Выбрали первую вершину пути(1). Поменяли ключ стартовой вершины на 0. Убрали ее из кучи, так как ее ключ минимален.
 
|width="100%"|key[] : [<tex>0</tex>, <tex>inf</tex>, <tex>inf</tex>, <tex>inf</tex>, <tex>inf</tex>]
 
Q : [2, 3, 4, 5]
 
 
вершина с минимальным ключом : <tex>1</tex> ключ 0
 
 
p[] : [1]
 
 
edges[]: <tex>-</tex>
 
|[[Файл:Prim21.jpg|center|300px]]
 
|-
 
|style="background:#f9f9f9" width="30%"|3) Смотрим на детей вершины (1). Расставляем им ключи. Находим в куче вершину с минимальным ключом(3). Удаляем ее из кучи, добавляем в ответ.
 
|width="100%"|key[] : [0, <tex>inf</tex>, 7, 14, <tex>inf</tex>]
 
Q : [2, 4, 5]
 
 
вершина с минимальным ключом : 3 с ключом 7
 
 
p[] : [1, 3]
 
 
edges: [(1, 3)] 
 
|[[Файл:Prim22.jpg|center|300px]]
 
|-
 
|style="background:#f9f9f9" width="30%"|4)Смотрим на детей вершины (3). Расставляем им ключи. Находим в куче вершину с минимальным ключом(2).Удаляем ее из кучи, добавляем в ответ.
 
|width="100%"|key[] : [0, <tex>inf</tex>, 7, 14, 71]
 
Q : [2, 5]
 
 
вершина с минимальным ключом : 4 с ключом 14
 
 
p[] : [1, 3, 4]
 
 
edges: [(1, 3), (4, 1)] 
 
|[[Файл:Prim23.jpg|center|300px]]
 
|-
 
|style="background:#f9f9f9" width="30%"|5)Смотрим на детей вершины (4). Расставляем им ключи. Находим в куче вершину с минимальным ключом(2).Удаляем ее из кучи, добавляем в ответ.
 
|width="100%"|key[] : [0, 4, 7, 14, 71]
 
Q :[5]
 
 
вершина с минимальным ключом : 2 с ключом 4
 
 
p[] : [1, 3, 4, 2]
 
 
edges: [(1, 3), (4, 1), (4, 2)]
 
|[[Файл:Prim24.jpg|center|300px]]
 
|-
 
|style="background:#f9f9f9" width="30%"|6)Смотрим на детей вершины (2). Расставляем им ключи. Находим в куче вершину с минимальным ключом(5).Удаляем ее из кучи, добавляем в ответ.
 
|width="100%"|key[] : [0, 4, 7, 14, 52]
 
Q :[]
 
 
вершина с минимальным ключом : 5 с ключом 52
 
 
p[] : [1, 3, 4, 2, 5]
 
edges: [(1, 3), (4, 1), (4, 2), (2, 5)]
 
|[[Файл:Prim25.jpg|center|300px]]
 
|}
 
  
 
== См. также ==
 
== См. также ==

Версия 23:11, 31 декабря 2011

Алгоритм Прима — алгоритм поиска минимального остовного дерева (minimum spanning tree, MST) во взвешенном неориентированном связном графе.

Идея

Данный алгоритм очень похож на алгоритм Дейкстры. Будем последовательно строить поддерево [math]F[/math] ответа в графе [math]G[/math], поддерживая приоритетную очередь [math]Q[/math] из вершин [math]G \setminus F[/math], имеющую ключом для вершины [math]v[/math] величину [math]\min\limits_{u \in VF, uv \in EG}w(uv)[/math] (вес минимального ребра из вершин [math]F[/math] в вершину [math]v[/math]). Также для каждой вершины очереди будем хранить [math]p(v)[/math] — вершину [math]u[/math], на которой достигается минимум в определении ключа. Дерево [math]F[/math] поддерживается неявно, и его ребра — это пары [math]\left(v,p(v)\right)[/math], где [math]v \in G \setminus \{r\} \setminus Q[/math], а [math]r[/math] — корень [math]F[/math]. Изначально [math]F[/math] пусто, в очереди все вершины с ключами [math]+\infty[/math]. Выберём произвольную вершину [math]r[/math] и присвоим её ключу [math]0[/math]. На каждом шаге будем извлекать минимальную вершину [math]v[/math] из приоритетной очереди и релаксировать все ребра [math]vu[/math], такие что [math]u \in Q[/math], выполняя при этом операцию [math]\text{decrease-key}[/math] над очередью и обновление [math]p(v)[/math]. Ребро [math]\left(v,p(v)\right)[/math] при этом добавляется к ответу.

Реализация

[math]\text{Prim}(G, w)[/math]
   [math]for[/math] [math]v \in V[G][/math]
       [math] key[v] \leftarrow \infty [/math]
       [math]p[v] \leftarrow \text{NIL}[/math]
   [math]r \leftarrow [/math] произвольная вершина в [math]V[G][/math]
   [math]key[r] \leftarrow 0 [/math]
   [math]Q \leftarrow V[G] [/math]
   [math]while[/math] [math] Q \neq \emptyset [/math]
       [math]v \leftarrow \text{extract-min}(Q) [/math]
       [math]for[/math] [math] u \in Adj[v] [/math]
           [math]if[/math] [math]u \in Q[/math] и [math]key[u] \gt  w(v, u) [/math]
               [math] p[u] \leftarrow v [/math]
               [math]key[u] \leftarrow w(v, u)[/math]
               [math]\text{decrease-key}(Q, u, key[u]) [/math]

Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.

Корректность

По поддерживаемым инвариантам после извлечения вершины [math]v[/math] ([math]v \neq r[/math]) из [math]Q[/math] ребро [math]\left(v,p(v)\right)[/math] является ребром минимального веса, пересекающим разрез [math]\left(F,Q\right)[/math]. Значит, по лемме о безопасном ребре, оно безопасно. Алгоритм построения MST, добавляющий безопасные ребра, причём делающий это ровно [math]|V|-1[/math] раз, корректен.

Оценка производительности

Производительность алгоритма Прима зависит от выбранной реализации приоритетной очереди, как и в алгоритме Дейкстры. Извлечение минимума выполняется [math]V[/math] раз, релаксация — [math]O(E)[/math] раз.

Структура данных для приоритетной очереди Асимптотика времени работы
Наивная реализация [math]O(V^2+E)[/math]
Двоичная куча [math]O(E\log{V})[/math]
Куча Фибоначчи [math]O(V\log{V}+E)[/math]


См. также

Визуализация алгоритма

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

Литература

  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — с.653 — 656.— ISBN 978-5-8459-0857-5 (рус.)