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

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

Описание

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

Вход

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

Выход

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

Реализация

Обозначения

• $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$ 
$v \gets\ Extract.min(Q)$ 
Пока $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)$

См. также

• Алгоритм Краскала

Ссылки

• Описание и реализация Алгоритма Прима
• ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ : Минимальные остовные деревья