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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Первая версия)
 
Строка 1: Строка 1:
 
Алгоритм Прима — алгоритм поиска [[Лемма о безопасном ребре#Минимальное остовное дерево|минимального остовного дерева]] (minimum spanning tree, MST) во взвешенном неориентированном связном графе.
 
Алгоритм Прима — алгоритм поиска [[Лемма о безопасном ребре#Минимальное остовное дерево|минимального остовного дерева]] (minimum spanning tree, MST) во взвешенном неориентированном связном графе.
  
==Идея==
+
== Идея ==
 
Данный алгоритм очень похож на [[алгоритм Дейкстры]]. Будем последовательно строить поддерево <tex>F</tex> ответа в графе <tex>G</tex>, поддерживая приоритетную очередь <tex>Q</tex> из вершин <tex>G \setminus F</tex>, имеющую ключом для вершины <tex>v</tex> <tex>\min\limits_{u \in F, uv \in EG}w(uv)</tex> (вес минимального ребра из вершин <tex>F</tex> в вершину <tex>v</tex>). Также для каждой вершины очереди будем хранить <tex>p(v)</tex> — вершину <tex>u</tex>, на которой достигается минимум в определении ключа. Дерево <tex>F</tex> поддерживается неявно, и равно <tex>\left\{\left(v,p(v)\right)|v \in G \setminus \{r\} \setminus Q\right\}</tex>, где <tex>r</tex> — корень <tex>F</tex>. Изначально <tex>F</tex> пусто, в очереди все вершины с ключами <tex>+\infty</tex>. Выберём произвольную вершину <tex>r</tex> и присвоим её ключу <tex>0</tex>. На каждом шаге будем извлекать минимальную вершину <tex>v</tex> из приоритетной очереди и релаксировать все ребра <tex>vu</tex>, такие что <tex>u \in Q</tex>, выполняя при этом DECREASE-KEY и обновление <tex>p(v)</tex>. Ребро <tex>\left(v,p(v)\right)</tex> при этом добавляется к ответу.
 
Данный алгоритм очень похож на [[алгоритм Дейкстры]]. Будем последовательно строить поддерево <tex>F</tex> ответа в графе <tex>G</tex>, поддерживая приоритетную очередь <tex>Q</tex> из вершин <tex>G \setminus F</tex>, имеющую ключом для вершины <tex>v</tex> <tex>\min\limits_{u \in F, uv \in EG}w(uv)</tex> (вес минимального ребра из вершин <tex>F</tex> в вершину <tex>v</tex>). Также для каждой вершины очереди будем хранить <tex>p(v)</tex> — вершину <tex>u</tex>, на которой достигается минимум в определении ключа. Дерево <tex>F</tex> поддерживается неявно, и равно <tex>\left\{\left(v,p(v)\right)|v \in G \setminus \{r\} \setminus Q\right\}</tex>, где <tex>r</tex> — корень <tex>F</tex>. Изначально <tex>F</tex> пусто, в очереди все вершины с ключами <tex>+\infty</tex>. Выберём произвольную вершину <tex>r</tex> и присвоим её ключу <tex>0</tex>. На каждом шаге будем извлекать минимальную вершину <tex>v</tex> из приоритетной очереди и релаксировать все ребра <tex>vu</tex>, такие что <tex>u \in Q</tex>, выполняя при этом DECREASE-KEY и обновление <tex>p(v)</tex>. Ребро <tex>\left(v,p(v)\right)</tex> при этом добавляется к ответу.
  
==Реализация==
+
== Реализация ==
 
  '''<tex>\text{MST\_Prim}(G, w)</tex>'''
 
  '''<tex>\text{MST\_Prim}(G, w)</tex>'''
 
   '''for''' (для) всех <tex>v \in V[G]</tex>
 
   '''for''' (для) всех <tex>v \in V[G]</tex>
Строка 21: Строка 21:
 
Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.  
 
Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.  
 
== Корректность ==
 
== Корректность ==
По поддерживаемым инвариантам после извлечения вершины <tex>v</tex> (<tex>v \neq r</tex>) из <tex>Q</tex> ребро <tex>\left(v,p(v)\right)</tex> является ребром минимального веса, пересекающим разрез <tex>\left(F,Q\right)</tex>. Значит, по [[Лемма о безопасном ребре|лемме о безопасном ребре]], оно безопасно.
+
По поддерживаемым инвариантам после извлечения вершины <tex>v</tex> (<tex>v \neq r</tex>) из <tex>Q</tex> ребро <tex>\left(v,p(v)\right)</tex> является ребром минимального веса, пересекающим разрез <tex>\left(F,Q\right)</tex>. Значит, по [[Лемма о безопасном ребре|лемме о безопасном ребре]], оно безопасно. Алгоритм построения MST, добавляющий безопасные ребра, причём делающий это ровно <tex>|V|-1</tex> раз, корректен.
  
==См. также==
+
== Оценка производительности ==
 +
Производительность алгоритма Прима зависит от выбранной реализации приоритетной очереди, как и в [[алгоритм Дейкстры|алгоритме Дейкстры]]. Извлечение минимума выполняется <tex>O(V)</tex> раз, релаксация — <tex>O(E)</tex> раз.
 +
 
 +
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=30%
 +
!style="background:#f2f2f2"|Структура данных для приоритетной очереди
 +
!style="background:#f2f2f2"|Асимптотика времени работы
 +
|-
 +
|style="background:#f9f9f9"|Наивная реализация
 +
|style="background:#f9f9f9"|<tex>O(V^2+E)</tex>
 +
|-
 +
|style="background:#f9f9f9"|Двоичная куча
 +
|style="background:#f9f9f9"|<tex>O(E\log{V})</tex>
 +
|-
 +
|style="background:#f9f9f9"|Куча Фибоначчи
 +
|style="background:#f9f9f9"|<tex>O(V\log{V}+E)</tex>
 +
|}
 +
 
 +
== См. также ==
 
* [[Алгоритм Краскала]]
 
* [[Алгоритм Краскала]]
  

Версия 19:11, 8 декабря 2010

Алгоритм Прима — алгоритм поиска минимального остовного дерева (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 F, uv \in EG}w(uv)[/math] (вес минимального ребра из вершин [math]F[/math] в вершину [math]v[/math]). Также для каждой вершины очереди будем хранить [math]p(v)[/math] — вершину [math]u[/math], на которой достигается минимум в определении ключа. Дерево [math]F[/math] поддерживается неявно, и равно [math]\left\{\left(v,p(v)\right)|v \in G \setminus \{r\} \setminus Q\right\}[/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], выполняя при этом DECREASE-KEY и обновление [math]p(v)[/math]. Ребро [math]\left(v,p(v)\right)[/math] при этом добавляется к ответу.

Реализация

[math]\text{MST\_Prim}(G, w)[/math]
  for (для) всех [math]v \in V[G][/math]
     do [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]
  while [math] Q \neq \emptyset [/math]
     do [math]u \leftarrow \text{EXTRACT-MIN}(Q) [/math]
        for (для) каждой вершины [math] v \in Adj[u] [/math]
           do if [math]v \in Q[/math] и [math]key[v] \gt  \omega(u, v) [/math]
              then [math] p[v] \leftarrow u [/math]
                   [math]key[v] \leftarrow \omega(u, v)[/math]
                   [math]\text{DECREASE-KEY}(Q, v) [/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]O(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 (рус.)