53
правки
Изменения
Первая версия
Алгоритм Прима — алгоритм поиска [[Лемма о безопасном ребре#Минимальное остовное дерево|минимального остовного дерева]] (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>\text{MST\_Prim}(G, w)</tex>'''
'''for''' (для) всех <tex>v \in V[G]</tex>
'''do''' <tex> key[v] \leftarrow \infty </tex>
<tex>p[v] \leftarrow \text{NIL}</tex>
<tex>r \leftarrow </tex> произвольная вершина в <tex>V[G]</tex>
<tex>key[r] \leftarrow 0 </tex>
<tex>Q \leftarrow V[G] </tex>
'''while''' <tex> Q \neq \emptyset </tex>
'''do''' <tex>u \leftarrow \text{EXTRACT-MIN}(Q) </tex>
'''for''' (для) каждой вершины <tex> v \in Adj[u] </tex>
'''do''' '''if''' <tex>v \in Q</tex> и <tex>key[v] > \omega(u, v) </tex>
'''then''' <tex> p[v] \leftarrow u </tex>
<tex>key[v] \leftarrow \omega(u, v)</tex>
<tex>\text{DECREASE-KEY}(Q, v) </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>. Значит, по [[Лемма о безопасном ребре|лемме о безопасном ребре]], оно безопасно.
==См. также==
* [[Алгоритм Краскала]]
== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — с.653 — 656.— ISBN 978-5-8459-0857-5 (рус.)
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
==Идея==
Данный алгоритм очень похож на [[алгоритм Дейкстры]]. Будем последовательно строить поддерево <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>'''
'''for''' (для) всех <tex>v \in V[G]</tex>
'''do''' <tex> key[v] \leftarrow \infty </tex>
<tex>p[v] \leftarrow \text{NIL}</tex>
<tex>r \leftarrow </tex> произвольная вершина в <tex>V[G]</tex>
<tex>key[r] \leftarrow 0 </tex>
<tex>Q \leftarrow V[G] </tex>
'''while''' <tex> Q \neq \emptyset </tex>
'''do''' <tex>u \leftarrow \text{EXTRACT-MIN}(Q) </tex>
'''for''' (для) каждой вершины <tex> v \in Adj[u] </tex>
'''do''' '''if''' <tex>v \in Q</tex> и <tex>key[v] > \omega(u, v) </tex>
'''then''' <tex> p[v] \leftarrow u </tex>
<tex>key[v] \leftarrow \omega(u, v)</tex>
<tex>\text{DECREASE-KEY}(Q, v) </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>. Значит, по [[Лемма о безопасном ребре|лемме о безопасном ребре]], оно безопасно.
==См. также==
* [[Алгоритм Краскала]]
== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — с.653 — 656.— ISBN 978-5-8459-0857-5 (рус.)
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
