Редактирование: Алгоритм Прима

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
'''Алгоритм Прима''' (англ. ''Prim's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Минимальное остовное дерево|минимального остовного дерева]] (англ. ''minimum spanning tree, MST'') во взвешенном [[Основные определения теории графов#Неориентированные графы | неориентированном связном графе]].
+
'''Алгоритм Прима'''(англ. ''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> при этом добавляется к ответу.
+
Данный алгоритм очень похож на [[алгоритм Дейкстры]]. Будем последовательно строить поддерево <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>v</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> при этом добавляется к ответу.
  
 
== Реализация ==
 
== Реализация ==
<font color=green>// <tex>G</tex> {{---}} исходный граф</font>
+
  '''function''' Prim(G, w)
<font color=green>// <tex>w</tex> {{---}} весовая функция</font>
+
     '''for''' каждой вершины v из графа G
  '''function''' <tex>\mathtt{primFindMST}():</tex>
+
         key[v] = <tex>\infty</tex>
     '''for''' <tex>v \in V(G)</tex>
+
         p[v] = NIL
         <tex>\mathtt{key}[v]\ =\ \infty</tex>
+
     r = произвольная вершина графа G
         <tex>\mathtt{p}[v]\ =</tex> ''null''
+
     key[r] = 0  
     <tex>r\ =</tex> произвольная вершина графа <tex>G</tex>
+
     Q.push(все вершины графа G)  
     <tex>\mathtt{key}[r]\ =\ \mathtt{0}</tex>
+
     '''while''' Q не пуста
     <tex>Q.\mathtt{push}(V(G))</tex>
+
         v = extractMin(Q)  
     '''while not''' <tex>Q.\mathtt{isEmpty()}</tex>
+
         '''for''' всех u смежных с v
         <tex>v\ =\ Q.\mathtt{extractMin}()</tex>
+
             '''if''' u in Q and key[u] > w(v, u)
         '''for''' <tex>vu \in E(G)</tex>
+
                 p[u] = v
             '''if''' <tex>u \in Q</tex> '''and''' <tex>\mathtt{key}[u] > w(v, u)</tex>
+
                 key[u] = w(v, u)
                 <tex>\mathtt{p}[u]\ =\ v</tex>
+
                 Q.decreaseKey(u, key[u])
                 <tex>\mathtt{key}[u]\ =\ w(v, u)</tex>
 
                 <tex>Q.\mathtt{decreaseKey}(u, \mathtt{key}[u])</tex>
 
  
 
Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.<br>
 
Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.<br>
Чтобы упростить операцию <tex>\mathrm{decreaseKey}</tex> можно написать кучу на основе [[АВЛ-дерево | сбалансированного бинарного дерева поиска]]. Тогда просто удалим вершину и добавим ее обратно уже с новым ключом. Асимптотика таких преобразований <tex>O(\log n)</tex>. Если же делать с [[Двоичная_куча | бинарной кучей]], то вместо операции <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>, что хорошо только на разреженных графах.
+
Операцию <tex>decreaseKey</tex> сделать для приоритетной очереди на [[Двоичная_куча | двоичной куче]] немного проблематично, поэтому есть два варианта. Первый, написать приоритетную очередь на какой-то сложной куче, например, [[Биномиальная_куча | биноминальной]] или [[Фибоначчиева_куча |фибоначчиевой]]. Второй, изменять значение ключа вершины, для которой вызвали <tex>decreaseKey</tex>, непосредственно в куче, после чего делать процедуру просеивания вверх для этой вершины. Для быстрого доступа к позиции вершины в куче, нужно дополнительно хранить указатель на эту позицию и не забывать его менять во время изменения кучи.
  
 
==Пример==
 
==Пример==
 
Рассмотрим работу алгоритма на примере графа.
 
Рассмотрим работу алгоритма на примере графа.
Пусть произвольно выбранная вершина это вершина a.
+
Пусть произвольно выбранная вершина это вершина a.
 
{| cellpadding = "20" class = "wikitable"
 
{| cellpadding = "20" class = "wikitable"
 
! Изображение !! Множество вершин !! Описание
 
! Изображение !! Множество вершин !! Описание
Строка 38: Строка 36:
 
| <tex> 0 </tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
 
| <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''', которые будут добавлены в ответ.
+
|style="padding-left: 1em" | Извлечём из множества вершину '''a''', так как её приоритет минимален.<br/>Рассмотрим смежные с ней вершины '''b''', '''c''', и '''e'''. <br/>Обновим их приоритеты, как веса соответствующих рёбер '''ab''', '''ac''' и '''ae''', которые будут добавленны в ответ.
 
|-
 
|-
 
|[[Файл:Mst_prima_2.png|200px]]
 
|[[Файл:Mst_prima_2.png|200px]]
Строка 47: Строка 45:
 
| <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex>\infty</tex> || <tex> 1 </tex>
 
| <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''', которое будет добавлено в ответ.
+
|style="padding-left: 1em" |Теперь минимальный приоритет у вершины '''е'''.<br/> Извлечём её и рассмотрим смежные с ней вершины '''a''', '''c''', и '''d'''.<br/>Изменим приоритет только у вершины '''d''', так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ea''' и '''ec''', и установим приоритет вершины '''d''' равный весу ребра '''ed''', которое будет добавленно в ответ.
 
|-
 
|-
 
|[[Файл:Mst_prima_3.png|200px]]
 
|[[Файл:Mst_prima_3.png|200px]]
Строка 56: Строка 54:
 
| <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex> 7 </tex> || <tex> 1 </tex>
 
| <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'''.
+
|style="padding-left: 1em" |После извлечения вершины '''b''' ничего не изменится, так как приоритеты вершин '''a''' и '''с''' меньше,<br/>чем веса у соответствующих рёбер '''ba''' и '''bc'''. Однако, после извлечения следующей вершины - '''c''',<br/>будет обновлён приоритет у вершины '''d''' на более низкий (равный весу ребра '''cd''') и в ответе ребро '''ed''' будет заменено на '''cd'''.
 
|-
 
|-
 
|[[Файл:Mst_prima_4.png|200px]]
 
|[[Файл:Mst_prima_4.png|200px]]
Строка 65: Строка 63:
 
| <tex> 0 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex> 2 </tex> || <tex> 1 </tex>
 
| <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/>которые не были бы рассмотрены
+
|style="padding-left: 1em" |Далее будет рассмотрена следующая вершина - '''d''', но ничего не изменится,<br/>так как приоритеты вершин '''e''' и '''с''' меньше, чем веса у соответствующих рёбер '''de''' и '''dc'''.<br/>После этого алгоритм завершит работу, так как в заданном множестве не останется вершин,<br/>которые не были бы рассмотрены
 
|}
 
|}
  
 
== Корректность ==
 
== Корректность ==
По поддерживаемым инвариантам после извлечения вершины <tex>v\ (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>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> раз, корректен.
  
 
== Оценка производительности ==
 
== Оценка производительности ==
Строка 94: Строка 92:
 
== Источники информации ==
 
== Источники информации ==
 
*Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — с.653 — 656.— ISBN 978-5-8459-0857-5 (рус.)
 
*Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ, 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://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://en.wikipedia.org/wiki/Prim%27s_algorithm Wikipedia - Prim's algorithm]
*[http://e-maxx.ru/algo/mst_prim MAXimal :: algo :: Минимальное остовное дерево. Алгоритм Прима]
+
*[http://e-maxx.ru/algo/mst_prim e-maxx - Минимальное остовное дерево. Алгоритм Прима]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Остовные деревья ]]
 
[[Категория: Остовные деревья ]]
[[Категория: Построение остовных деревьев]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: