На этом шаге рассмотрим реализацию функции поиска в ширину.

Для построения увеличивающего пути используется механизм очереди от истока

 Put(0); {Поместить в очередь начальную вершину} 
  Find:=false; 
  while (BegQ<=EndQ) and not Find do {Пока очередь не пуста и путь не найден} 
  begin 
    Get(i); {Взять вершину i из очереди}

Вначале идет попытка увеличить путь за счет прямых дуг, здесь:

массив color[i] хранит пометки для всех вершин (включена/нет в увеличивающийся путь);
массив back[k] хранит номер вершины, из которой пришли в вершину k в увеличивающем пути;
переменная Find получает значение true, если увеличивающий путь достиг стока (a[i,j] = Finish).

j:=1;   {номер дуги из вершины i} 
while (a[i,j]>0) and not Find do {пока дуги не кончились}
begin 
   if (color[a[i,j]]=WHITE) and (cf[i,a[i,j]]>0) then {если вершина a[i,j] свободна} 
   begin
     Put(a[i,j]); {поставить ее в очередь} 
     back[a[i,j]]:=i; {в вершину a[i,j] - из вершины i} 
     color[a[i,j]]:=GRAY; {пометить вершину a[i,j] как использованную}
     Find := a[i,j]=Finish; 
   end; 
   inc(j); {взять следующую дугу} 
end;

Далее делаем попытку увеличить путь за счет обратных дуг

j:=1; {номер дуги из вершины i}
while (ia[i,j]>=0) and not Find do  {пока дуги не кончились} 
begin 
   if (color[ia[i,j]]=WHITE) and (cf[i,ia[i,j]]>0) then 
   {если вершина a[i,j] свободна}
    begin
       Put(ia[i,j]); {поставить ее в очередь} 
       back[ia[i,j]]:=i; {в вершину a[i,j] - из вершины i} 
       color[ia[i,j]]:=GRAY; {пометить вершину a[i,j] }
                               {как использованную}
       Find :=ia[i,j]=Finish;
    end;
    inc(j); {взять следуюшую дугу} 
end;

После выхода из цикла построения увеличивающего пути остается только восстановить увеличивающий путь в массив path, используя массив back. Попутно подсчитываются количество дуг в увеличивающем пути KR и минимальный добавляемый поток Cmin.

  KR:=0; 
  i:=Finish; {Начинаем с конца} 
  Cmin:=maxint; 
  while (i<>0) do {Пока не начало} 
  begin 
    Inc(KR); {Увеличиваем количество дуг в пути} 
    path[KR]:=i; {Заносим номер предыдущей вершины} 
    i:=back[i]; {Меняем текущую вершину} 
    if Cmin>cf[i,path[KR]] then Cmin:=cf[i,path[KR]]; {Минимальный добавляемый поток} 
  end;
  path[KR+1]:=0;
  ExistPath:=Find;

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

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