На этом шаге рассмотрим алгоритм Прима для решения поставленной задачи.

Идея алгоритма Прима заключается в следующем: пусть А — это множество ребер части остова, растущей от пустого множества ребер к минимальному остовному дереву. Формирование множества A может начинаться с произвольной вершины, называемой корневой. Для определенности в реализации в качестве корневой выбирается вершина 1.

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

Для эффективной организации выбора нужного для добавления ребра используется очередь с приоритетами, в которой хранятся все вершины, еще не попавшие в дерево A. При этом каждая вершина i снабжена также приоритетом — специальной характеристикой Key[i], которая равна минимальному весу ребер, соединяющих вершину i с вершинами из А.

Более формально алгоритм Прима может быть записан следующим образом:

Ставим в очередь Q все вершины исходного графа 
Устанавливаем для всех вершин Key[i] = бесконечность (MaxD) 
Заносим в дерево А вершину 1: 
	key[1] = 0 - расстояние от нее до вершин дерева А 
	Pred[1] = 0 - у корневой вершины нет предка 
Пока очередь Q не пуста 
	Выбираем из очереди вершину U такую, для которой расстояние 
		от нее до вершин из множества А минимально 
	Для каждой вершины V соседней с U 
		  (то есть в графе имеется ребро (U,V))
		если V находится в очереди и D[U,V] < key[V] 
		то  Pred[V] = U 
		    key[V] = D[U,V]

Ниже приведена реализация алгоритма Прима:

procedure MinTree; 
Const 
  MaxD = lel6; {"бесконечность"} 
  Free =0;
  Used =1; 
var 
  Lbl : array [1..MaxN] of byte; 
  Key : array [1..MaxN] of single; 
  u, v : byte;
  Min : single; 
begin 
  for i := 1 to N do 
  begin 
   key[i]:=MaxD; 
   Lbl[i]:=Free; { Все вершины в очереди}
  end; 
  Key[1]:= 0; { Начнем построение с остова с 1-й вершины} 
  Pred[1]:= 0; { У 1-й вершины нет предка} 
  for i:=1 to N do { Для всех вершин } 
  begin 
    Min:=MaxD; 
    for j:=1 to N do { Находим вершину, } 
      if (Lbl[j]=Free) and (Key[j] < Min)  then { ближайшую к остову } 
      begin 
        u:=j; 
        Min:=Key[j]; 
      end;
    Lbl[u]:=Used; { Помечаем ее как использованную} 
    for v:=1 to N do { Для всех оставшихся в очереди вершин} 
     if (Lbl[v]=Free) and (D[u,v] < Key[v]) then 
     begin { Пересчитываем } 
        Key[v]:=D[u,v]; { расстояние до растущего остова }
        Pred[v]:=u;  { Переустанавливаем предка}
     end; 
  end; 
end;

На следующем шаге рассмотрим программный код реализации данной задачи.

Предыдущий шаг Содержание Следующий шаг