Поиск в ширину

Для обхода в ширину нам понадобится очередь. Очередь - это структура данных, над которой можно выполнять четыре операции: очищать ее, добавлять элемент в ее конец, получать ее первый элемент и удалять первый элемент из очереди. Мы реализуем очередь массивом Q из N элементов и двумя счетчиками: Ql и Qr, которые будут указывать положение в массиве соответственно начала и конца очереди. Вначале, когда очередь пуста, Ql=1 и Qr=0. Реализация операций над очередью очевидна.

Мы будем обходить вершины начиная с данной вершины и обойдем только те из них, которые достижимы из нее. Как и при обходе в глубину, заведем массив V из N элементов, но теперь в нем будут записаны целые числа. i-й элемент массива будет равен -1, если i-я вершина еще не была рассмотрена; иначе в i-м элементе будет находиться длина кратчайшего пути от данной до i-й вершины. Обход в ширину очень часто используется для отыскания кратчайших путей из некоторой вершины во все остальные. В этом случае, поскольку сам обход не требуется, требуется убрать из алгоритма строку Writeln(Cur). Порядок обхода вершин в ширину будет таким: сначала данная вершина, потом все вершины, которые с ней смежны, потом все вершины, наикратчайший путь от которых до данной имеет длину 2, и т. д. В конце обхода будут располагаться вершины, наиболее удаленные от данной.

Ход работы алгоритма:

Вначале мы добавляем в очередь первую вершину. Затем, пока очередь не станет пустой, мы рассматриваем первую вершину в очереди, обходим все ранее не обойденные вершины, с ней смежные, и удаляем первую вершину в очереди. При обходе каждой вершины мы добавляем ее в конец очереди.

Реализация алгоритма:

const
  MaxN = 100;

var
  N : Integer;
  G : array [1 .. MaxN,1 .. MaxN] of Boolean;
  V : array [1 .. MaxN] of Integer;
  Q : array [1 .. MaxN] of Integer;
  Ql,Qr : Integer;

procedure BFS(A : Integer);
var
  Cur : Integer;
  B : Integer;
begin
  FillChar(V,sizeof(V),255);
  Ql:=1;
  Qr:=1;
  Q[1] := A;
  V[A] := 0;
  while Qr >= Ql do
  begin
    Cur:=Q[Ql];
    Inc(Ql);
    Writeln(Cur);
    for B := 1 to N do
      if G[Cur,B] and (V[b]=-1) then
        begin
          V[b]:=V[Cur]+1;
          Inc(Qr);
          Q[Qr]:=B;
        end;
  end;
end;

Оценим время работы алгоритма обхода в ширину. Главный цикл выполняется не более чем N раз (каждая итерация соответствует 1 элементу очереди, и каждая вершина бывает в очереди не более 1 раза), и время выполнения каждой его итерации O(N); значит, общее время работы O(N2), как и для обхода в глубину; для хранения очереди требуется O(N) памяти. При реализации графа списками смежности алгоритм требует O(M+N) времени.