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

Описание

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

Вход

• Связный неориентированный граф

Выход

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

Реализация

Обозначения

•  — расстояние от -й вершины до построенного дерева
•  — предок -й вершины, то есть такая вершина , что легчайшее из всех рёбер соединяющее i с вершиной из построенного дерева.
•  — вес ребра
•  — приоритетная очередь вершин графа, где ключ —
•  — множество ребер минимального остовного дерева

Псевдокод

 {} 
Для каждой вершины    
 
 
 
 
 
Пока  не пуста
 Для каждой вершины  смежной с 
  Если  и   
   
   
 
 

Оценка

Асимптотика алгоритма зависит от способа хранения графа и способа хранения вершин, не входящих в дерево. Если приоритетная очередь реализована как обычный массив , то выполняется за , а стоимость операции составляет . Если представляет собой бинарную пирамиду, то стоимость снижается до , а стоимость возрастает до . При использовании фибоначчиевых пирамид операция выполняется за , а за .

См. также

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

Ссылки

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