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

Описание

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

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

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

Пример

Изображение	Множество выбранных вершин U	Ребро (u, v)	Множество невыбранных вершин V \ U	Описание
	{}		{A,B,C,D,E,F,G}	Исходный взвешенный граф. Числа возле ребер показывают их веса, которые можно рассматривать как расстояния между вершинами.
	{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 .
	{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 .
	{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.
	{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 .
	{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 .
	{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 .
	{A,B,C,D,E,F,G}	(B,C) = 8 цикл (D,B) = 9 цикл (D,E) = 15 цикл (F,E) = 8 цикл (F,G) = 11 цикл	{}	Выбраны все вершины, минимальное остовное дерево построено (выделено зелёным). В этом случае его вес равен 39.

Реализация

Обозначения

• ${\displaystyle d[i]}$ — расстояние от ${\displaystyle i}$ -й вершины до построенного дерева
• ${\displaystyle p[i]}$ — предок ${\displaystyle i}$ -й вершины, то есть такая вершина ${\displaystyle u}$ , что ${\displaystyle (u,i)}$ легчайшее из всех рёбер, соединяющее i с вершиной из построенного дерева.
• ${\displaystyle w(i,j)}$ — вес ребра ${\displaystyle (i,j)}$
• ${\displaystyle Q}$ — приоритетная очередь вершин графа, где ключ — ${\displaystyle d[i]}$
• ${\displaystyle T}$ — множество ребер минимального остовного дерева

Псевдокод

 ${\displaystyle T\gets }$ {} 
Для каждой вершины  ${\displaystyle i\in V}$  
 ${\displaystyle d[i]\gets \infty }$
 ${\displaystyle p[i]\gets nil}$
${\displaystyle d[1]\gets 0}$ 

${\displaystyle Q\gets V}$ 
${\displaystyle v\gets \ Extract.Min(Q)}$  

Пока ${\displaystyle Q}$ не пуста
  Для каждой вершины ${\displaystyle u}$ смежной с ${\displaystyle v}$
    Если ${\displaystyle u\in Q}$ и ${\displaystyle w(v,u)<d[u]}$  
      ${\displaystyle d[u]\gets w(v,u)}$
      ${\displaystyle p[u]\gets v}$
  ${\displaystyle v\gets Extract.Min(Q)}$
 ${\displaystyle T\gets T+(p[v],v)}$

Оценка

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

Способ представления приоритетной очереди и графа	Асимптотика
Массив d, списки смежности (матрица смежности)	${\displaystyle O(V^{2})}$
Бинарная пирамида, списки смежности	${\displaystyle O((V+E)\log V)=O(E\log V)}$
Фибоначчиева пирамида, списки смежности	${\displaystyle O(E+V\log V)}$

См. также

• Минимальное остовное дерево
• Остовное дерево
• Алгоритм Борувки
• Алгоритм Дейкстры
• Алгоритм обратного удаления
• Алгоритм Краскала

Литература

• V. Jarník: O jistém problému minimálním [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57-63. (чешск.)
• R. C. Prim: Shortest connection networks and some generalizations . In: Bell System Technical Journal , 36 (1957), pp. 1389—1401 (англ.)
• and : Finding minimum spanning trees . In: , 5 (Dec. 1976), pp. 724—741 (англ.)
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . Introduction to Algorithms , Third Edition. MIT Press, 2009. ISBN 0-262-03384-4 . Section 23.2: The algorithms of Kruskal and Prim, pp. 631—638. (англ.)

Ссылки

• (неопр.) . Дата обращения: 7 июля 2009. Архивировано из 11 января 2014 года.