Шаг 79.
Алгоритмы.
Реализация алгоритма Прима

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

    Архив с примером можно взять здесь.

program pr;
Const 
  MaxN = 100; 
var 
  N, i, j : 1..MaxN; 
  X, Y : array [1..MaxN] of longint; 
  D : array [1..MaxN,1..MaxN] of single; 
  Pred : array [1..MaxN] of byte; 
procedure InputData;
 var 
  i, j : 1..MaxN; 
begin  
  assign (input,'input.txt');
  reset(input);
  readln(N); 
  for  i := 1 to  N do 
    readln(x[i],y[i]);
  close(input); 
  for  i := 1 to  N do  
    for  j := 1 to  N do  
      D[i, j] := sqrt(sqr(x[i] - x[j]) + sqr(y[i] - y[j])); 
end; 
procedure  OutputData; 
var  
  Answer : single; 
  i, j : 1..MaxN; 
begin  
  Answer := 0;
  for  i := 2 to  N do  
    Answer := Answer + D[i, Pred[i]]; 
  assign(output, 'output.txt'); 
  rewrite(output);
  writeln(Answer:0:2); 
  close(output); 
end;
procedure MinTree; 
Const 
  MaxD = 1e16; {"бесконечность"} 
  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;
begin 
  InputData; 
  MinTree;
  OutputData; 
end.

    На следующем шаге рассмотрим алгоритм Крускала.




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