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

Алгоритм Прима, алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 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 — множество ребер минимального остовного дерева

Псевдокод:

{}

Для каждой вершины

Пока Q не пуста

Для каждой вершины u смежной с v

Если и w(v,u) < d[u]

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

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