Изменения

'''Алгоритм Прима ''' (англ. ''Prim's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Минимальное остовное дерево|минимального остовного дерева]] (англ. ''minimum spanning tree, MST'') во взвешенном [[Основные определения теории графов#Неориентированные графы | неориентированном связном графе]].

Данный алгоритм очень похож на [[алгоритм Дейкстры]]. Будем последовательно строить поддерево <tex>F</tex> ответа в графе <tex>G</tex>, поддерживая [[Дискретная_математика,_алгоритмы_и_структуры_данных#.D0.9F.D1.80.D0.B8.D0.BE.D1.80.D0.B8.D1.82.D0.B5.D1.82.D0.BD.D1.8B.D0.B5_.D0.BE.D1.87.D0.B5.D1.80.D0.B5.D0.B4.D0.B8 | приоритетную очередь ]] <tex>Q</tex> из вершин <tex>G \setminus F</tex>, имеющую в которой ключом для вершины <tex>v</tex> является <tex>\min\limits_{u \in V(F), uv \in EGE(G)}w(uv)</tex> (— вес минимального ребра из вершин <tex>F</tex> в вершину вершины <tex>vG \setminus F</tex>). Также для каждой вершины в очереди будем хранить <tex>p(v)</tex> — вершину <tex>u</tex>, на которой достигается минимум в определении ключа. Дерево <tex>F</tex> поддерживается неявно, и равно его ребра — это пары <tex>\left\{\left(v,p(v)\right)|</tex>, где <tex>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>, выполняя при этом операцию <tex>\text{DECREASE-KEYdecreaseKey}</tex> над очередью и обновление <tex>p(v)</tex>. Ребро <tex>\left(v,p(v)\right)</tex> при этом добавляется к ответу.

Предположим у нас есть множества вершин и ребер ориентированного взвешенного графа. <tex> V </tex> - вершины. <tex> E </tex> - ребра.В <tex>F</tex> мы будем неявно хранить поддерево ответа. Для каждой вершины в ответе мы будем хранить вершину Ребра дерева восстанавливаются из которой мы в нее пришлиего неявного вида после выполнения алгоритма.То есть <tex>(v,previos(v))</texbr>Хранить <tex>V</tex> мы будем в приоритетной очереди. Ключом для вершины <tex>v</tex> будет вес минимального ребра из v в вершины уже содержащиеся в ответе. То есть <tex>v</tex> Чтобы упростить операцию <tex>\min\limits_mathrm{u \in F, uv \in EdecreaseKey}w(uv)</tex>.Сначала выберем первую вершину искомого остового можно написать кучу на основе [[АВЛ-дерево | сбалансированного бинарного деревапоиска]]. Ее мы можем выбрать рандомно. Положим ее в ответ и Тогда просто удалим из <tex>V</tex>.На каждой итерации мы будем выбирать из <tex>V</tex> вершину и добавим ее обратно уже с минимальным новым ключом и добавлять ее к ответу, убирая ее из <tex>V</tex>. == Реализация == '''Асимптотика таких преобразований <tex>O(\text{Prim}(G, wlog n)</tex>''' <tex>for</tex> <tex>v \in V. Если же делать с [[GДвоичная_куча | бинарной кучей]</tex> <tex> key[v] \leftarrow \infty </tex> , то вместо операции <tex>p[v] \leftarrow \textmathrm{NILdecreaseKey}</tex> <tex>r \leftarrow </tex> произвольная вершина , будем всегда просто добавлять вершину с новым ключом, если из кучи достали вершину с ключом, значение которого больше чем у нее уже стоит, просто игнорировать. Вершин в куче будет не больше <tex>V[G]</tex> <tex>key[r] \leftarrow 0 </tex> <tex>Q \leftarrow V[G] </tex> <tex>whilen^2</tex> , следовательно, операция <tex> Q \neq \emptyset </tex> <tex>v \leftarrow \textmathrm{extract-minextractMin}(Q) </tex> будет выполняться за <tex>for</tex> <tex> u O(\in Adj[v] log n^2)</tex> , что равно <tex>if</tex> <tex>u O(\in Qlog n)</tex> и <tex>key[u] > w(v. Максимальное количество вершин, которое мы сможем достать, равняется количеству ребер, u) то есть </tex> <tex> p[u] \leftarrow v m</tex> , поэтому общая асимптотика составит <tex>key[u] O(m \leftarrow w(v, ulog n)</tex> <tex>\text{decrease-key}(Q, u, key[u]) </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>V</tex> раз, релаксация — <tex>O(E)</tex> раз.

|style="background:#f9f9f9"|[[Двоичная куча]]

|style="background:#f9f9f9"|Куча Фибоначчи[[Фибоначчиевы кучи|Фибоначчиева куча]]

== См. также ==

== Литература Источники информации ==* ''Кормен, Томас Х., ЛейзерсонКормен, Чарльз И., РивестЛейзерсон, Рональд Л.Ривест, Клиффорд Штайн Клиффорд'' '''— Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — с.653 — 656.— ISBN 978-5-8459-0857-5 (рус.)*[http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D1%80%D0%B8%D0%BC%D0%B0 Википедия — Алгоритм Прима]*[http://en.wikipedia.org/wiki/Prim%27s_algorithm Wikipedia — Prim's algorithm]*[http://e-maxx.ru/algo/mst_prim MAXimal :: algo :: Минимальное остовное дерево. Алгоритм Прима]