Стратегия поиска в глубину – идти «вглубь», пока это возможно, и возвращаться и искать другой путь, когда таких ребер нет.
Так делается, пока не обнаружены все вершины, достижимые из исходной.
Если после этого остаются необнаруженные вершины, можно выбрать одну из них и повторять процесс, пока не обнаружим все вершины графа.
Обнаружив впервые вершину v, смежную с u, мы отмечаем это событие, помещая в поле p [v] значение u.
Получается подграф предшествования (лес поиска в глубину), определенный так:Gp= (V, Ep), где
Ep = {(p[v],v) : vÎ V и p [v] ¹ NIL}
Алгоритм поиска используют цвета вершин.
Вначале каждая вершина – белая.
Будучи обнаруженной она становится серой.
Когда вершина полностью обработана (просмотрен список смежных с ней вершин), она становится черной.
При поиске в глубину на вершинах ставят метки времени.
Каждая вершина имеет две метки:
d[v] –вершина обнаружена (и сделана серой)
f[v] – закончена обработка (стала черной)
В процедуре DFS (поиск в глубину) метки времени – целые числа от 1 до 2 ôVô.
Для любой вершины u выполняется неравенство
d[u] < f[u]
Исходный граф может быть ориентированным или неориентированным.
Переменная time – глобальная переменная текущего времени
DFS(G)
1 for (для) всех вершин u Î V[G]
2 do color[u] ¬ БЕЛЫЙ
3 p [u] ¬ NIL
4 time ¬ 0
5 for (для) всех вершин u Î V[G]
6 do if color [u] = БЕЛЫЙ
7 then DFS-VISIT (u)
DFS-VISIT (u)
1 color [u] = СЕРЫЙ
2 d[u] ¬ time ¬ time + 1
3 for (для) всех v Î Adj [u]
4 do if color [v] = БЕЛЫЙ
5 then p[v] = u
6 DFS-VISIT (v)
7 color [u] = ЧЕРНЫЙ
8 f[u] ¬ time ¬ time + 1