Различные представления графа
Для реализации графа в виде списка инцидентности можно использовать следующий тип:
Type List = ^S;
S = record;
inf: Byte;
next: List;
end;
Тогда граф задается следующим образом:
Var Gr: array[1..n] of List;
Теперь обратимся к процедуре обхода графа. Это вспомогательный алгоритм, который позволяет просмотреть все вершины графа, проанализировать все информационные поля. Если рассматривать обход графа в глубину, то существуют два типа алгоритмов: рекурсивный и нерекурсивный.
На языке Pascal процедура обхода в глубину будет выглядеть следующим образом:
Procedure Obhod(gr: Graph; k: Byte);
Var g: Graph; l: List;
Begin
nov[k]:= false;
g:= gr;
While g^.inf <> k do
g:= g^.next;
l:= g^.smeg;
While l <> nil do begin
If nov[l^.inf] then Obhod(gr, l^.inf);
l:= l^.next;
End;
End;
Представление графа списком списков
Граф можно определить с помощью списка списков следующим образом:
Type List = ^Tlist;
Tlist = record
inf: Byte;
next: List;
end;
Graph = ^TGpaph;
TGpaph = record
inf: Byte;
smeg: List;
next: Graph;
end;
При обходе графа в ширину мы выбираем произвольную вершину и просматриваем сразу все вершины, смежные с ней.
Приведем процедуру обхода графа в ширину на псевдокоде:
Procedure Obhod2(v);
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;
