Для реализации графа в виде списка инцидентности можно использовать следующий тип: 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;