В алгоритме Прима растущая часть остова представляет собой дерево (множество ребер которого есть A). Формирование дерева начинается с произвольной корневой вершины r. На каждом шаге добавляется ребро наименьшего веса среди ребер, соединяющих веершины этого дерева с вершинами не из дерева. По следствию добавляемые ребра являются безопасными для A , так что в результате получается минимальный остов.
Алгоритм получает на вход связный граф G и корень r минимального покрывающего дерева. В ходе алгоритма все вершины, еще не попавшие в дерево, хранятся в очереди с приоритетами. Приоритет вершины v определяется значением key[v], которое равно минимальному весу ребер, соединяющих v с вершинами дерева A. (Если таких ребр нет, полагаем key[v] = ¥ ). Поле p [v] для вершин дерева указывает на родителя, а для вершины v Î Q указывает на вершину дерева, в которую ведет ребро веса key[v].
Множество ребер строящегося дерева явно не хранится; его можно восстановить как
A ={( v, p [v] ): vÎV \ {r} \ Q }
В конце работы алгоритма очередь Q пуста, а множество
A ={( v, p [v] ): vÎV \ {r} }
Есть множество ребер покрываюшего дерева
MST-PRIM (G, w, r)
1 Q ¬ V[G]
2 for (для) каждой вершины uÎ Q
3 do key[u]´
4 key[r]¬0
5 p [r] ¬NIL
6 while Q ¹ Æ
7 do u ¬ EXTRACT-MIN(Q)
8 for (для) каждой вершины vÎ Adj[u]
9 do if vÎQ и w(u,v) < key[v]
10 then p [v] ¬u
11 key[v] ¬ w(u,v)
Оценка времени работы алгоритма Прима
Если для организации очереди Q использовать двоичную кучу, инициализацию в строках 1-4 можно выполнить за время O(V).
Цикл выполняеется ôVôраз, и каждая операция EXTRACT-MIN занимает время O(log V), всего O(V log V).
Цикл в строках 8-11 выполняется в общей сложности O(E) раз. Проверку принадлежности в строке 9 внутри цикла можно реализовать за O(1).
Присваивание в строке 11 может быть выполнена за время O(log V).
Всего получаем O(V log V + E log V) = O( E log V).