Представление графа списком списков. Алгоритм обхода графа в ширину
Граф можно определить с помощью списка списков следующим образом:
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;