Изменения

'''Алгоритм Прима ''' (англ. ''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), (u,v) uv \in E(G)}\{w(u,vuv)\}</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> при этом добавляется к ответу.

'''<font color=green>// <tex>G</tex>\text{Prim{---}}(V, G, исходный граф</font> <font color=green>// <tex>w)</tex>{{---}} весовая функция</font> '''function''' <tex>for\mathtt{primFindMST}():</tex> '''for''' <tex>v \in V[(G])</tex> <tex> \mathtt{key}[v] \leftarrow =\ \infty </tex> <tex>\mathtt{p}[v] \leftarrow \text{NIL}=</tex>''null'' <tex>r \leftarrow =</tex> <tex>произвольная вершина в </tex>графа <tex>V[G]</tex> <tex>\mathtt{key}[r] \leftarrow =\ \mathtt{0 }</tex> <tex>Q .\leftarrow mathtt{push}(V[(G] ))</tex> <tex> '''while</tex> not''' <tex> Q .\neq \emptyset mathtt{isEmpty()}</tex> <tex>u v\ =\leftarrow Q.\textmathtt{extract-minextractMin}(Q) </tex> <tex> '''for''' </tex> <tex> v vu \in Adj[u] E(G)</tex> <tex> '''if''' </tex> <tex>v u \in Q</tex> <tex>'''and</tex> ''' <tex>\mathtt{key}[vu] > \omegaw(v, u, v) </tex> <tex>then</tex> <tex> \mathtt{p}[vu] \leftarrow u =\ v</tex> <tex>\mathtt{key}[vu] \leftarrow =\omegaw(v, u, v)</tex> <tex>Q.\textmathtt{decrease-keydecreaseKey}(Qu, v\mathtt{key}[u]) </tex>Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.

==Пример работы Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма==.<br>Чтобы упростить операцию <tex>\mathrm{decreaseKey}</tex> можно написать кучу на основе [[Файл:Prim1АВЛ-дерево | сбалансированного бинарного дерева поиска]].jpgТогда просто удалим вершину и добавим ее обратно уже с новым ключом. Асимптотика таких преобразований <tex>O(\log n)</tex>. Если же делать с [[Двоичная_куча |right|400px|thumb|Граф "звезда" бинарной кучей]], то вместо операции <tex>\mathrm{decreaseKey}</tex>, будем всегда просто добавлять вершину с новым ключом, если из кучи достали вершину с расставленными весами ключом, значение которого больше чем у нее уже стоит, просто игнорировать. Вершин в куче будет не больше <tex>n^2</tex>, следовательно, операция <tex>\mathrm{extractMin}</tex> будет выполняться за <tex>O(\log n^2)</tex>, что равно <tex>O(\log n)</tex>. Максимальное количество вершин, которое мы сможем достать, равняется количеству ребер ]], то есть <tex>m</tex>, поэтому общая асимптотика составит <tex>O(m \log n)</tex>, что хорошо только на разреженных графах.

Таблица соответствует работе ==Пример==Рассмотрим работу алгоритма на графе с картинкипримере графа.Пусть произвольно выбранная вершина — это вершина a.{| border="1" cellpadding="520" cellspacingclass ="0wikitable" style="text-align:center" width=30%! Изображение !! Множество вершин !! Описание

|colspan="6"[[Файл:Mst_prima_1.png| key[200px]]|colspan{| width="2100%" rowspanstyle ="2text-align: center"| '''a''' || '''b''' || '''c''' || p[]'''d''' || '''e'''

|rowspan="3"<tex> 0 </tex> |style="background:#f9f9f9"|№ шага<tex>\infty</tex> |style="background:#f9f9f9"|1<tex>\infty</tex> |style="background:#f9f9f9"|2<tex>\infty</tex> |style="background:#f9f9f9"|3<tex>\infty</tex>|style="background:#f9f9f9"|4}|style="backgroundpadding-left:#f9f9f91em"|5Извлечём из множества вершину '''a''', так как её приоритет минимален.<br/>Рассмотрим смежные с ней вершины '''b''', '''c''', и '''e'''. <br/>Обновим их приоритеты, как веса соответствующих рёбер '''ab''', '''ac''' и '''ae''', которые будут добавлены в ответ.

|style="background[[Файл:#f9f9f9"Mst_prima_2.png|200px]]|1){|stylewidth="background:#FFFF00100%"|<tex>\infty </tex>|style="backgroundtext-align:#FFFF00center"|<tex>\infty </tex>a |style="background:#FFFF00"|<tex>\infty </tex>'''b''' |style="background:#FFFF00"|<tex>\infty </tex>'''c''' |style="background:#FFFF00"|<tex>\infty </tex>'''d''' |style="background:#f9f9f9"|<tex>-</tex>'''e'''

|style="background:#f9f9f9"|2) |style="background:#FF0000"|<tex> 0</tex> |style="background:#FFFF00"|<tex>\infty 3 </tex>|style="background:#FFFF00"|<tex>\infty 4 </tex>|style="background:#FFFF00"|<tex>\infty </tex>|style="background:#FFFF00"|<tex>\infty 1 </tex>|}|style="backgroundpadding-left:#f9f9f91em"|1Теперь минимальный приоритет у вершины '''е'''.<br/> Извлечём её и рассмотрим смежные с ней вершины '''a''', '''c''', и '''d'''.<br/>Изменим приоритет только у вершины '''d''', так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ea''' и '''ec''', и установим приоритет вершины '''d''' равный весу ребра '''ed''', которое будет добавлено в ответ.

|style="background[[Файл:#f9f9f9"Mst_prima_3.png|3)200px]]|{|stylewidth="background:#FF0000100%"|0|style="backgroundtext-align:#FFFF00center"|<tex>\infty </tex>a |style="background:#FF0000"|7'''b''' |style="background:#FFFF00"|14'''c''' |style="background:#FFFF00"|<tex>\infty </tex> '''d''' |style="background:#f9f9f9"|1 3e

|style="background:#f9f9f9"<tex> 0 </tex> |4) |style="background:#FF0000"<tex> 3 </tex> |0|style="background:#FFFF00"|<tex>\infty 4 </tex>|style="background:#FF0000"|<tex> 7</tex> |style="background:#FF0000"|14<tex> 1 </tex>|style="background:#FFFF00"|71}|style="backgroundpadding-left:#f9f9f91em"|4 1 3После извлечения вершины '''b''' ничего не изменится, так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ba''' и '''bc'''. Однако, после извлечения следующей вершины {{---}} '''c''',<br/>будет обновлён приоритет у вершины '''d''' на более низкий (равный весу ребра '''cd''') и в ответе ребро '''ed''' будет заменено на '''cd'''.

|style="background[[Файл:#f9f9f9"Mst_prima_4.png|5)200px]]|{|stylewidth="background:#FF0000100%"|0|style="backgroundtext-align:#FF0000center"|2a |style="background:#FF0000"|7b |style="background:#FF0000"|14c |style="background:#FFFF00"|71'''d''' |style="background:#f9f9f9"|2 4 1 3e

|style="background:#f9f9f9"<tex> 0 </tex> ||6) <tex> 3 </tex> |style="background:#FF0000"|0<tex> 4 </tex> |style="background:#FF0000"|<tex> 2</tex> |style="background:#FF0000"|7|style="background:#FF0000"|14<tex> 1 </tex>|style="background:#FF0000"|71}|style="backgroundpadding-left:#f9f9f91em"|5 2 4 1 3Далее будет рассмотрена следующая вершина {{---}} '''d''', но ничего не изменится,<br/>так как приоритеты вершин '''e''' и '''с''' меньше, чем веса у соответствующих рёбер '''de''' и '''dc'''.<br/>После этого алгоритм завершит работу, так как в заданном множестве не останется вершин,<br/>которые не были бы рассмотрены

По поддерживаемым инвариантам после извлечения вершины <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 :: Минимальное остовное дерево. Алгоритм Прима]