Изменения

'''Алгоритм Прима''' (англ. ''Prim's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Минимальное остовное дерево|минимального остовного дерева]] (англ. ''minimum spanning tree, MST'') во взвешенном [[Основные_определения_теории_графовОсновные определения теории графов#.D0.9D.D0.B5.D0.BE.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B Неориентированные графы | неориентированном связном графе]].

Данный алгоритм очень похож на [[алгоритм Дейкстры]]. Будем последовательно строить поддерево <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 E(G)}w(uv)</tex> — вес минимального ребра из вершин <tex>F</tex> в вершины <tex>G \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{decreaseKey}</tex> над очередью и обновление <tex>p(v)</tex>. Ребро <tex>\left(v,p(v)\right)</tex> при этом добавляется к ответу.

<span stylefont color="color: green">//<tex>G </tex> {{-- -}} исходный граф<br/font> <font color=green>//<tex>w </tex> {{--- }} весовая функция</spanfont> '''function''' <tex>\mathtt{primFindMST}():</tex> '''for''' <tex>v '''\in''' V(G)</tex> <tex>\mathtt{key}[v] \ = <tex>\ \infty</tex> <tex>\mathtt{p}[v] \ = </tex> ''null'' <tex>r \ = </tex> произвольная вершина графа <tex>G</tex> <tex>\mathtt{key}[r] \ = \ \mathtt{0 }</tex> <tex>Q.\mathtt{push}(V(G) )</tex> '''whilenot''' not <tex>Q.\mathtt{isEmpty()}</tex> <tex>v \ = \ Q.\mathtt{extractMin}() </tex> '''for''' <tex>vu '''\in''' E(G)</tex> '''if''' <tex>u '''\in''' Q </tex> '''and''' <tex>\mathtt{key}[u] > w(v, u)</tex> <tex>\mathtt{p}[u] \ = \ v</tex> <tex>\mathtt{key}[u] \ = \ w(v, u)</tex> <tex>Q.\mathtt{decreaseKey}(u, \mathtt{key}[u])</tex>

Сделать Чтобы упростить операцию <tex>\mathrm{decreaseKey}</tex> для приоритетной очереди можно написать кучу на основе [[Двоичная_куча АВЛ-дерево | двоичной кучесбалансированного бинарного дерева поиска]] немного проблематично, поэтому есть два варианта. Первый, написать приоритетную очередь на какой-то сложной куче, например, Тогда просто удалим вершину и добавим ее обратно уже с новым ключом. Асимптотика таких преобразований <tex>O(\log n)</tex>. Если же делать с [[Биномиальная_куча Двоичная_куча | биноминальнойбинарной кучей]]. Второй, изменять то вместо операции <tex>\mathrm{decreaseKey}</tex>, будем всегда просто добавлять вершину с новым ключом, если из кучи достали вершину с ключом, значение ключа вершиныкоторого больше чем у нее уже стоит, для которой вызвали просто игнорировать. Вершин в куче будет не больше <tex>decreaseKeyn^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>, нужно дополнительно хранить указатель что хорошо только на эту позицию и не забывать его менять во время изменения кучиразреженных графах.

|style="padding-left: 1em" | Извлечём из множества вершину '''a''', так как её приоритет минимален.<br/>Рассмотрим смежные с ней вершины '''b''', '''c''', и '''e'''. <br/>Обновим их приоритеты, как веса соответствующих рёбер '''ab''', '''ac''' и '''ae''', которые будут добавленны добавлены в ответ.

|style="padding-left: 1em" |Теперь минимальный приоритет у вершины '''е'''.<br/> Извлечём её и рассмотрим смежные с ней вершины '''a''', '''c''', и '''d'''.<br/>Изменим приоритет только у вершины '''d''', так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ea''' и '''ec''', и установим приоритет вершины '''d''' равный весу ребра '''ed''', которое будет добавленно добавлено в ответ.

|style="padding-left: 1em" |После извлечения вершины '''b''' ничего не изменится, так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ba''' и '''bc'''. Однако, после извлечения следующей вершины {{- --}} '''c''',<br/>будет обновлён приоритет у вершины '''d''' на более низкий (равный весу ребра '''cd''') и в ответе ребро '''ed''' будет заменено на '''cd'''.

|style="padding-left: 1em" |Далее будет рассмотрена следующая вершина {{- --}} '''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> раз, корректен.