1632
правки
Изменения
м
rollbackEdits.php mass rollback
'''Алгоритм Прима''' (англ. ''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 Неориентированные графы | неориентированном связном графе]].
== Идея ==
<font color=green>// <tex>G</tex> {{---}} исходный граф</font>
<font color=green>// <tex>w</tex> {{---}} весовая функция</font>
'''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> '''while 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>
Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.<br>
| <tex> 0 </tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
|}
|style="padding-left: 1em" | Извлечём из множества вершину '''a''', так как её приоритет минимален.<br/>Рассмотрим смежные с ней вершины '''b''', '''c''', и '''e'''. <br/>Обновим их приоритеты, как веса соответствующих рёбер '''ab''', '''ac''' и '''ae''', которые будут добавленны добавлены в ответ.
|-
|[[Файл:Mst_prima_2.png|200px]]
| <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex>\infty</tex> || <tex> 1 </tex>
|}
|style="padding-left: 1em" |Теперь минимальный приоритет у вершины '''е'''.<br/> Извлечём её и рассмотрим смежные с ней вершины '''a''', '''c''', и '''d'''.<br/>Изменим приоритет только у вершины '''d''', так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ea''' и '''ec''', и установим приоритет вершины '''d''' равный весу ребра '''ed''', которое будет добавленно добавлено в ответ.
|-
|[[Файл:Mst_prima_3.png|200px]]
| <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex> 7 </tex> || <tex> 1 </tex>
|}
|style="padding-left: 1em" |После извлечения вершины '''b''' ничего не изменится, так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ba''' и '''bc'''. Однако, после извлечения следующей вершины {{- --}} '''c''',<br/>будет обновлён приоритет у вершины '''d''' на более низкий (равный весу ребра '''cd''') и в ответе ребро '''ed''' будет заменено на '''cd'''.
|-
|[[Файл:Mst_prima_4.png|200px]]
| <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex> 2 </tex> || <tex> 1 </tex>
|}
|style="padding-left: 1em" |Далее будет рассмотрена следующая вершина {{- --}} '''d''', но ничего не изменится,<br/>так как приоритеты вершин '''e''' и '''с''' меньше, чем веса у соответствующих рёбер '''de''' и '''dc'''.<br/>После этого алгоритм завершит работу, так как в заданном множестве не останется вершин,<br/>которые не были бы рассмотрены
|}
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
[[Категория: Построение остовных деревьев]]
