Алгоритм Прима

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Описание[править | править вики-текст]

Построение начинается с дерева, включающего в себя одну (произвольную) вершину. В течение работы алгоритма дерево разрастается, пока не охватит все вершины исходного графа. На каждом шаге алгоритма к текущему дереву присоединяется самое лёгкое из рёбер, соединяющих вершину из построенного дерева и вершину не из дерева.

Вход[править | править вики-текст]

  • Связный неориентированный граф G(V,E)

Выход[править | править вики-текст]

  • Множество T рёбер минимального остовного дерева

Пример[править | править вики-текст]

Изображение Множество выбранных вершин 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.

Реализация[править | править вики-текст]

Обозначения[править | править вики-текст]

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

Псевдокод[править | править вики-текст]

 T \gets   {} 
Для каждой вершины   i \in V   
d[i] \gets \infty p[i] \gets nil d[1] \gets 0
Q \gets V
Пока Q не пуста v \gets\ Extract.min(Q)
Для каждой вершины u смежной с v Если u \in Q и w(v,u) < d[u] d[u] \gets w(v,u) p[u] \gets v  v \gets Extract.Min(Q)  T \gets T+(p[v],v)

Оценка[править | править вики-текст]

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

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

См. также[править | править вики-текст]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]