120
правок
Изменения
Нет описания правки
==Пример==
Задан неориентированный связный граф, требуется построить в нём минимальное остовное дерево.<br/>Создадим новый граф, содержащий все вершины из заданного графа, но не содержащий рёбер.<br/>Этот новый граф будет ответом, его множество рёбер будет изменено по ходу выполнения алгоритма.<br/>Создадим новое множество вершин с внешними значениями - приоритетами, из которого будем извлекать минимум.<br/>Заполним все приоритеты этого множества бесконечностью.<br/>Выберем любую вершину, от которой будет начато построение минимального остовного дерева (в примере это вершина '''a''').<br/>Установим приоритет этой вершины равный нулю.{| border = 1 cellspacing = 2 cellpadding = 5 class = "wikitable"
! Изображение !! Множество вершин !! Описание
|-
|[[Файл:Mst_prima_1.png|200px]]
|
{|width="100%"
| '''a''' || '''b''' || '''c''' || '''d''' || '''e'''
|-
| <tex> 0 </tex> || <tex> \inf </tex> || <tex> \inf </tex> || <tex> \inf </tex> || <tex> \inf </tex>
|}
| Извлечём из множества вершину '''a''', так как её приоритет минимален, и рассмотрим её соседей .<br/>Рассмотрим смежные с ней вершины '''b''', '''c''', и '''e'''. <br/>Обновим их приоритеты и добавим в ответ рёбра , как веса соответствующих рёбер '''ab''', '''ac''', и '''ae''', которые будут добавленны в ответ.
|-
|[[Файл:Mst_prima_2.png|200px]]
|
{|width="100%"
| <s>a</s> || '''b''' || '''c''' || '''d''' || '''e'''
|-
| <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex> \inf </tex> || <tex> 1 </tex>
|}
| Теперь минимальный приоритет у вершины '''е'''. <br/> Извлечём её и рассмотрим её соседейсмежные с ней вершины '''a''', '''c''', и '''d'''.<br/>Изменим приоритет только у вершины '''d''',так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ea''' и '''ec''', и добавим в ответ ребро установим приоритет вершины '''d''' равный весу ребра '''ed''', которое будет добавленно в ответ.
|-
|[[Файл:Mst_prima_3.png|200px]]
|
{|width="100%"
| <s>a</s> || '''b''' || '''c''' || '''d''' || <s>e</s>
|-
| <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex> 7 </tex> || <tex> 1 </tex>
|}
| После извлечения вершины '''b''' ничего не изменится, так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ba''' и '''bc'''. Однако, после извлечения следующий следующей вершины - '''c''',<br/>будет обновлён потенциал приоритет у вершины '''d''' на более низкий (равный весу ребра '''cd''') и в ответе ребро '''ed''' будет заменено на '''cd'''.
|-
|[[Файл:Mst_prima_4.png|200px]]
|
{|width="100%"
| <s>a</s> || <s>b</s> || <s>c</s> || '''d''' || <s>e</s>
|-
| <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex> 2 </tex> || <tex> 1 </tex>
|}
| Далее будет рассмотрена следующая вершина - '''d''', но ничего не изменится,<br/>так как приоритеты вершин '''e''' и '''с''' меньше, чем веса у соответствующих рёбер '''de''' и '''dc'''.<br/>После этого алгоритм завершит работу, так как в заданном множестве не останется вершин, <br/>которые не были бы рассмотрены,<br/>алгоритм завершит работу, так как минимальное остовное дерево будет построено.
|}
|}
== См. также ==* [[Алгоритм КраскалаПрима]]* [http://www.mincel.com/java/prim.html Визуализатор алгоритма[Алгоритм Борувки]]
== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — с.653 — 656.— ISBN 978-5-8459-0857-5 (рус.)
==Ссылки==
* [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/prim-2003 Визуализатор алгоритма №1]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/mst-2005 Визуализатор алгоритма №2]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/mst-2006 Визуализатор алгоритма №3]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
