3. Представление графа списком списков. Алгоритм обхода графа в ширину

3. Представление графа списком списков. Алгоритм обхода графа в ширину

Граф можно определить с помощью списка списков следующим образом:

Type List = ^Tlist;

Tlist = record

inf : Byte;

next : List;

end;

Graph = ^TGpaph;

TGpaph = record

inf : Byte;

smeg : List;

next : Graph;

end;

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

Приведем процедуру обхода графа в ширину на псевдокоде:

Procedure Obhod2(v);

{величины spisok, nov – глобальные}

Begin

queue = O;

queue <= v;

nov[v] = False;

While queue <> O do

Begin

p <= queue;

For u in spisok(p) do

If nov[u] then

Begin

nov[u] := False;

queue <= u;

End;

End;

End;