Write (t)

Procedure DEPTH( v );

End.

End ;

Procedure DEPTH_R(v) ;

begin NOWY[v]:= False; write(v) ;

for u Î СПИСОК[v] do

if NOWY[u] then DEPTH_R(u) ;

Основная программа поиска имеет вид.

var NOWY : array [1..n] of boolean;

begin for vÎV do NOWY[v]:= True ;

for vÎV do

if NOWY[v] then DEPTH_R(v)

В первом цикле программы производится инициализация массива Nowy. Далее для первой непросмотренной вершины вызывается процедура поиска. Если граф – связный, то после возврата в основную программу поиск будет закончен. В противном случае при первом вызове процедуры DEPTH_R будут просмотрены все вершины одной компоненты связности графа, затем поиск повторится, начиная с первой непросмотренной вершины. Таким образом, обращение к процедуре DEPTH_R(v) из основной программы происходит всякий раз при переходе к очередной компоненте связности графа.

Например, рассмотрим несвязный граф.

Рис. 3.2

Начнем поиск с начальной вершины 1. При вызове процедуры DEPTH_R(1) получаем следующую последовательность вершин: 1, 2, 6, 3, после чего происходит выход из процедуры в основную программу, т.к. список смежности исходной вершины исчерпан. При следующем вызове процедуры просмотр начнется с первой непросмотренной вершины 4, принадлежащей следующей компоненте связности графа.

Таким образом, для произвольного графа алгоритм работает корректно, то есть будут просмотрены все вершины графа, причем каждая не более одного раза.

Оценим вычислительную сложность рекурсивного варианта алгоритма. В качестве основной операции, по числу выполнений которой определяется трудоемкость алгоритма, выберем вызов процедуры DEPTH_R.

В основной программе она вызывается не более n раз. Внутри самой процедуры ее вызов в каждой вершине осуществляется столько раз, сколько эта вершина имеет смежных, или сколько ребер ей инцидентны. Так как каждое ребро инцидентно двум вершинам, то число вызовов не более 2m. Следовательно, вычислительная сложность алгоритма можно оценить как

.

Нерекурсивный поиск. Приведем нерекурсивный вариант процедуры поиска в глубину, использующий механизм стека, который организуется программистом (“вручную”). Обычно такой вариант требует меньше памяти и работает быстрее, чем рекурсивный, хотя и сложнее по реализации.

Всюду в дальнейшем мы будем использовать следующие обозначения:

1) СТЕК Ü v, ОЧЕРЕДЬ Ü v – поместить вершину v в СТЕК или ОЧЕРЕДЬ;

2) v Ü СТЕК; v Ü ОЧЕРЕДЬ – извлечь вершину v из СТЕКА или ОЧЕРЕДИ.

3) top(Массив) – первый элемент массива (стека, списка или иного).

4) down(Массив) – последний элемент массива.

5) x:= top(СТЕК) – переписать в переменную х первый элемент стека, не извлекая его.

6) Next(Массив) – следующий по порядку элемент массива.

begin СТЕК:= Æ; СТЕК Ü v;

NOWY[v]:= False; write(v);{вершина просмотрена}

while СТЕК<>Æ do

begin t:=top(СТЕК);

P:= top(СПИСОК[t]);

while(P<>down(СПИСОК[t]))and(not Nowy[P])

do P:= Next(СПИСОК[t]);

if P<>down(СПИСОК[t])then

{найдена новая вершина}

begin t:=P; СТЕКÜt; NOWY[t]:= False;