Представление графа списком инцидентности. Алгоритм обхода графа в глубину
Для реализации графа в виде списка инцидентности можно использовать следующий тип:
Type List = ^S;
S = record;
inf : Byte;
next : List;
end;
Тогда граф задается следующим образом:
Var Gr : array[1 n] of List;
Теперь обратимся к процедуре обхода графа. Это вспомогательный алгоритм, который позволяет просмотреть все вершины графа, проанализировать все информационные поля. Если рассматривать обход графа в глубину, то существуют два типа алгоритмов: рекурсивный и нерекурсивный.
При рекурсивном алгоритме обхода графа в глубину мы берем произвольную вершину и, отыскиваем произвольную непросмотренную (новую) вершину v, смежную с ней. Затем принимаем вершину v за неновую и отыскиваем любую смежную с ней новую вершину. Если же у какой-либо вершины нет более новых непросмотренных вершин, то полагаем эту вершину использованной и возвращаемся на уровень выше в ту вершину, из которой попали в нашу использованную вершину. Обход продолжается таким образом до тех пор, пока в графе не останется новых непросмотренных вершин.
На языке 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;
Примечание
В данной процедуре при описании типа Graph имелось в виду описание графа списком списков. Массив nov[i] – специальный массив, i-ый элемент которого равен True, если i-ая вершина не просмотрена, и False – в противном случае.
Также часто используется нерекурсивный алгоритм обхода. В этом случае рекурсия заменяется на стек. Как только вершина просмотрена, она помещается в стек, а использованной она становится, когда больше нет новых вершин, смежных с ней.