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

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

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

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

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

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

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

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

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

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

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

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