Изменения

'''Алгоритм Прима''' (англ. ''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 VFV(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(v,p(v)\right)</tex>, где <tex>v \in G \setminus \{r\} \setminus Q</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{---}}(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>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>v \leftarrow =\ Q.\textmathtt{extract-minextractMin}(Q) </tex> <tex>'''for''' </tex> <tex> u vu \in Adj[v] E(G)</tex> <tex>'''if</tex> ''' <tex>u \in Q</tex> и '''and''' <tex>\mathtt{key}[u] > w(v, u) </tex> <tex> \mathtt{p}[u] \leftarrow =\ v </tex> <tex>\mathtt{key}[u] \leftarrow =\ w(v, u)</tex> <tex>Q.\textmathtt{decrease-keydecreaseKey}(Q, u, \mathtt{key}[u]) </tex>Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.

== Корректность ==Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.<br>По поддерживаемым инвариантам после извлечения вершины Чтобы упростить операцию <tex>v\mathrm{decreaseKey}</tex> можно написать кучу на основе [[АВЛ-дерево | сбалансированного бинарного дерева поиска]]. Тогда просто удалим вершину и добавим ее обратно уже с новым ключом. Асимптотика таких преобразований <tex>O(\log n)</tex>. Если же делать с [[Двоичная_куча | бинарной кучей]], то вместо операции <tex>v \neq rmathrm{decreaseKey}</tex>) , будем всегда просто добавлять вершину с новым ключом, если из кучи достали вершину с ключом, значение которого больше чем у нее уже стоит, просто игнорировать. Вершин в куче будет не больше <tex>Qn^2</tex> ребро , следовательно, операция <tex>\leftmathrm{extractMin}</tex> будет выполняться за <tex>O(v,p(v)\rightlog n^2)</tex> является ребром минимального веса, пересекающим разрез что равно <tex>\leftO(F,Q\rightlog n)</tex>. ЗначитМаксимальное количество вершин, по [[Лемма о безопасном ребре|лемме о безопасном ребре]]которое мы сможем достать, оно безопасно. Алгоритм построения MSTравняется количеству ребер, добавляющий безопасные ребрато есть <tex>m</tex>, причём делающий это ровно поэтому общая асимптотика составит <tex>|V|-1O(m \log n)</tex> раз, корректенчто хорошо только на разреженных графах.

== Оценка производительности Пример==Производительность Рассмотрим работу алгоритма Прима зависит от выбранной реализации приоритетной очереди, как и в [[алгоритм Дейкстры|алгоритме Дейкстры]]на примере графа. Извлечение минимума выполняется <tex>V</tex> раз, релаксация Пусть произвольно выбранная вершина — <tex>O(E)</tex> разэто вершина a. {| bordercellpadding ="120" cellpaddingclass ="5wikitable" cellspacing! Изображение !! Множество вершин !! Описание|-|[[Файл:Mst_prima_1.png|200px]]|{| width="0100%" style="text-align:center" width=30%!style="background:#f2f2f2"|Структура данных для приоритетной очереди!style="background:#f2f2f2"'''a''' || '''b''' || '''c''' || '''d''' ||Асимптотика времени работы'''e'''

|style="background:#f9f9f9"<tex> 0 </tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>|Наивная реализация}|style="backgroundpadding-left:#f9f9f91em"|Извлечём из множества вершину '''a''', так как её приоритет минимален.<texbr/>O(V^2+E)Рассмотрим смежные с ней вершины '''b''', '''c''', и '''e'''. <br/tex>Обновим их приоритеты, как веса соответствующих рёбер '''ab''', '''ac''' и '''ae''', которые будут добавлены в ответ.

|style="background[[Файл:#f9f9f9"Mst_prima_2.png|200px]]|Двоичная куча{|width="100%" style="backgroundtext-align:#f9f9f9center"| a || '''b''' || '''c''' |<tex>O(E\log{V})</tex>| '''d''' || '''e'''

|style="background:#f9f9f9"<tex> 0 </tex> |Куча Фибоначчи|style="background:#f9f9f9"<tex> 3 </tex> || <tex> 4 </tex> ||<tex>O(V\log{V}+E)infty</tex> || <tex> 1 </tex>

  ==Пример работы алгоритма== {| border="1" cellpadding="3" cellspacing="0" style="textpadding-alignleft:center1em" width=70%|Теперь минимальный приоритет у вершины '''е'''.<br/> Извлечём её и рассмотрим смежные с ней вершины '''a''', '''c''', и '''d'''.<br/>Изменим приоритет только у вершины '''d''', так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ea''' и '''ec''', и установим приоритет вершины '''d''' равный весу ребра '''ed''', которое будет добавлено в ответ.

|rowspan[[Файл:Mst_prima_3.png|200px]]|{| width="1100%"style = "text-align: center"|№ шагаa || '''b''' || '''c''' || '''d''' |состояние|графe

|style="background:#f9f9f9" width="30%"|1) Получаем на вход граф, все вершины находятся в куче, ключи всех вершин <tex>inf0 </tex>.|width="150%"|key[] : [<tex>inf3 </tex>, || <tex>inf4 </tex>, || <tex>inf7 </tex>, || <tex>inf1 </tex>, <tex>inf</tex>]Q |}|style="padding-left: [11em" |После извлечения вершины '''b''' ничего не изменится, 2так как приоритеты вершин '''a''' и '''с''' меньше, 3, 4, 5] вершина с минимальным ключом : <texbr/>чем веса у соответствующих рёбер '''ba''' и '''bc'''. Однако, после извлечения следующей вершины {{-</tex> p[] : <tex>-</tex>  edges[] : <tex>-}} '''c''',<br/tex>|[[Файл:Prim20будет обновлён приоритет у вершины '''d''' на более низкий (равный весу ребра '''cd''') и в ответе ребро '''ed''' будет заменено на '''cd'''.jpg|center|300px]]

|style="background[[Файл:#f9f9f9" width="30%"Mst_prima_4.png|200px]]|2) Выбрали первую вершину пути(1). Поменяли ключ стартовой вершины на 0. Убрали ее из кучи, так как ее ключ минимален.{|width="100%"|key[] style = "text-align: [<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>center"|[[Файл:Prim21.jpga || b || c || '''d''' |center|300px]]e

|style="background:#f9f9f9" width="30%"<tex> 0 </tex> ||<tex> 3) Смотрим на детей вершины (1). Расставляем им ключи. Находим в куче вершину с минимальным ключом(3). Удаляем ее из кучи, добавляем в ответ. </tex> || <tex> 4 </tex> |width="100%"|key[] : [0, <tex>inf2 </tex>, 7, 14, || <tex>inf1 </tex>]Q |}|style="padding-left: [21em" |Далее будет рассмотрена следующая вершина {{---}} '''d''', но ничего не изменится,<br/>так как приоритеты вершин '''e''' и '''с''' меньше, чем веса у соответствующих рёбер '''de''' и '''dc'''.<br/>После этого алгоритм завершит работу, 4так как в заданном множестве не останется вершин, 5]<br/>которые не были бы рассмотрены|}

p[] : [1== Оценка производительности ==Производительность алгоритма Прима зависит от выбранной реализации приоритетной очереди, 3]как и в алгоритме Дейкстры. Извлечение минимума выполняется <tex>V</tex> раз, релаксация — <tex>O(E)</tex> раз.

edges{| border="1" cellpadding="5" cellspacing="0" style="text-align: [(1, 3)] center" width=30%!style="background:#f2f2f2"|[[ФайлСтруктура данных для приоритетной очереди!style="background:Prim22.jpg|center#f2f2f2"|300px]]Асимптотика времени работы

|style="background:#f9f9f9" width="30%"|4)Смотрим на детей вершины (3). Расставляем им ключи. Находим в куче вершину с минимальным ключом(2).Удаляем ее из кучи, добавляем в ответ. Наивная реализация|widthstyle="100%background:#f9f9f9"|key[] : [0, <tex>infO(V^2+E)</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).Удаляем ее из кучи, добавляем в ответ. [[Двоичная куча]]|widthstyle="100%background:#f9f9f9"|key[] : [0, 4, 7, 14, 71]Q :[5] вершина с минимальным ключом : 2 с ключом 4 p[] : [1, 3, 4, 2] edges: [<tex>O(1, 3E\log{V}), (4, 1), (4, 2)] |[[Файл:Prim24.jpg|center|300px]]</tex>

|style="background:#f9f9f9" width="30%"|6)Смотрим на детей вершины (2). Расставляем им ключи. Находим в куче вершину с минимальным ключом(5).Удаляем ее из [[Фибоначчиевы кучи, добавляем в ответ. |Фибоначчиева куча]]|widthstyle="100%background:#f9f9f9"|key[] : [0, 4, 7, 14, 52]Q :[] вершина с минимальным ключом : 5 с ключом 52 p[] : [1, 3, 4, 2, 5]edges: [(1, 3), (4, 1), (4, 2), <tex>O(2, 5V\log{V}+E)] |[[Файл:Prim25.jpg|center|300px]]</tex>

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

== Литература Источники информации ==* ''Кормен, Томас Х., ЛейзерсонКормен, Чарльз И., РивестЛейзерсон, Рональд Л.Ривест, Клиффорд Штайн Клиффорд'' '''— Алгоритмы: построение и анализ''', 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 :: Минимальное остовное дерево. Алгоритм Прима]