Лекции - Структуры и алгоритмы компьютерной обработки данных / 17.Поиск в ширину. Построение эйлерова цикла

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

Для обработки вершин используется очередь. Сначала в очередь добавляется начальная вершина. Затем из очереди выбирается вершина и добавляются все вершины, смежные с ней и ранее не рассмотренные.

procedure bfs(v: integer);

var k: integer;

begin

inc(NumPre); pre[v]:=NumPre; Push(q,v);

While not(empty(q)) do

begin v:=Pop(q);

for k:=1 to N do

if (A[v,k] > 0) and (pre[k]=0) then

begin P[k]:=v; Push(q,k);

inc(NumPre); pre[v]:=NumPre;

end;

end;

end;

Поиск в ширину находит кратчайшие пути от начальной вершины до остальных в той же компоненте связности.

Эйлеров цикл

При поиске в глубину (не помечая вершины) будем удалять ребра, по которым прошли. После возврата в вершину ее номер добавляется в стек.

procedure Euler(v: integer);

var k: integer;

begin

for k:=1 to N do

if (A[v,k] > 0) then

begin

A [v,k]:=0; // A[k,v]:=0;

Euler (k);

end;

inc(Num); path[Num]:=v;

end;