Русская Википедия:Алгоритм Прима

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.

Описание

На вход алгоритма подаётся связный неориентированный граф. Для каждого ребра задаётся его стоимость.

Сначала берётся произвольная вершина и находится ребро, инцидентное данной вершине и обладающее наименьшей стоимостью. Найденное ребро и соединяемые им две вершины образуют дерево. Затем, рассматриваются рёбра графа, один конец которых — уже принадлежащая дереву вершина, а другой — нет; из этих рёбер выбирается ребро наименьшей стоимости. Выбираемое на каждом шаге ребро присоединяется к дереву. Рост дерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа.

Результатом работы алгоритма является остовное дерево минимальной стоимости.

Пример

Изображение Множество выбранных вершин U Ребро (u, v) Множество невыбранных вершин V \ U Описание
Файл:Prim Algorithm 0.svg {} {A,B,C,D,E,F,G} Исходный взвешенный граф. Числа возле ребер показывают их веса, которые можно рассматривать как расстояния между вершинами.
Файл:Prim Algorithm 1.svg {D} (D,A) = 5 V
(D,B) = 9
(D,E) = 15
(D,F) = 6		 {A,B,C,E,F,G} В качестве начальной произвольно выбирается вершина D. Каждая из вершин A, B, E и F соединена с D единственным ребром. Вершина A — ближайшая к D, и выбирается как вторая вершина вместе с ребром AD.
Файл:Prim Algorithm 2.svg {A,D} (D,B) = 9
(D,E) = 15
(D,F) = 6 V
(A,B) = 7		 {B,C,E,F,G} Следующая вершина — ближайшая к любой из выбранных вершин D или A. B удалена от D на 9 и от A — на 7. Расстояние до E равно 15, а до F — 6. F является ближайшей вершиной, поэтому она включается в дерево F вместе с ребром DF.
Файл:Prim Algorithm 3.svg {A,D,F} (D,B) = 9
(D,E) = 15
(A,B) = 7 V
(F,E) = 8
(F,G) = 11		 {B,C,E,G} Аналогичным образом выбирается вершина B, удаленная от A на 7.
Файл:Prim Algorithm 4.svg {A,B,D,F} (B,C) = 8
(B,E) = 7 V
(D,B) = 9 цикл
(D,E) = 15
(F,E) = 8
(F,G) = 11		 {C,E,G} В этом случае есть возможность выбрать либо C, либо E, либо G. C удалена от B на 8, E удалена от B на 7, а G удалена от F на 11. E — ближайшая вершина, поэтому выбирается E и ребро BE.
Файл:Prim Algorithm 5.svg {A,B,D,E,F} (B,C) = 8
(D,B) = 9 цикл
(D,E) = 15 цикл
(E,C) = 5 V
(E,G) = 9
(F,E) = 8 цикл
(F,G) = 11		 {C,G} Здесь доступны только вершины C и G. Расстояние от E до C равно 5, а до G — 9. Выбирается вершина C и ребро EC.
Файл:Prim Algorithm 6.svg {A,B,C,D,E,F} (B,C) = 8 цикл
(D,B) = 9 цикл
(D,E) = 15 цикл
(E,G) = 9 V
(F,E) = 8 цикл
(F,G) = 11		 {G} Единственная оставшаяся вершина — G. Расстояние от F до неё равно 11, от E — 9. E ближе, поэтому выбирается вершина G и ребро EG.
Файл:Prim Algorithm 7.svg {A,B,C,D,E,F,G} (B,C) = 8 цикл
(D,B) = 9 цикл
(D,E) = 15 цикл
(F,E) = 8 цикл
(F,G) = 11 цикл		 {} Выбраны все вершины, минимальное остовное дерево построено (выделено зелёным). В этом случае его вес равен 39.

Реализация

Обозначения

  • <math> d[i] </math> — расстояние от <math>i</math>-й вершины до построенного дерева
  • <math> p[i] </math> — предок <math>i</math>-й вершины, то есть такая вершина <math>u</math>, что <math>(u,i)</math> легчайшее из всех рёбер, соединяющее i с вершиной из построенного дерева.
  • <math>w(i,j)</math> — вес ребра <math>(i,j)</math>
  • <math>Q</math> — приоритетная очередь вершин графа, где ключ — <math>d[i]</math>
  • <math>T</math> — множество ребер минимального остовного дерева

Псевдокод

 <math> T \gets  </math> {} 
Для каждой вершины  <math> i \in V </math>  
 <math>d[i] \gets \infty </math>
 <math>p[i] \gets nil</math>
<math>d[1] \gets 0</math> 

<math>Q \gets V</math> 
<math>v \gets\ Extract.Min(Q) </math>  

Пока <math>Q </math> не пуста
  Для каждой вершины <math>u</math> смежной с <math>v</math>
    Если <math>u \in Q</math> и <math>w(v,u) < d[u]</math>  
      <math>d[u] \gets w(v,u)</math>
      <math>p[u] \gets v</math>
  <math> v \gets Extract.Min(Q)</math>
 <math> T \gets T+(p[v],v)</math>

Оценка

Асимптотика алгоритма зависит от способа хранения графа и способа хранения вершин, не входящих в дерево. Если приоритетная очередь <math>Q</math> реализована как обычный массив <math>d</math>, то <math>Extract.Min(Q)</math> выполняется за <math>O(n)</math>, а стоимость операции <math>d[u] \gets w(v, u)</math> составляет <math>O(1)</math>. Если <math>Q</math> представляет собой бинарную пирамиду, то стоимость <math>Extract.Min(Q)</math> снижается до <math>O(\log n)</math>, а стоимость <math>d[u] \gets w(v,u)</math> возрастает до <math>O(\log n)</math>. При использовании фибоначчиевых пирамид операция <math>Extract.Min(Q)</math> выполняется за <math>O(\log n)</math>, а <math>d[u] \gets w(v, u)</math> за <math>O(1)</math>.

Способ представления приоритетной очереди и графа Асимптотика
Массив d, списки смежности (матрица смежности) <math>O(V^2)</math>
Бинарная пирамида, списки смежности <math >O((V + E) \log V) = O(E \log V) </math>
Фибоначчиева пирамида, списки смежности <math> O(E + V \log V) </math>

См. также

Литература

Ссылки

Шаблон:Алгоритмы поиска на графах

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Алгоритм_Прима&oldid=8940160