Реализация поиска в глубину

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

В обоих алгоритмах, BFS и DFS, существуют различия между обнаружением узла v (когда алгоритм впервые видит узел при обнаружении ребра, ведущего к v) и проверкой узла v (когда перебираются все ребра, инцидентные v, что может приве- сти к обнаружению дальнейших узлов). Различия между BFS и DFS проявляются в особенностях чередования обнаружений и проверок.

В алгоритме BFS, приступая к проверке узла u в уровне Li, мы добавляли всех его вновь обнаруженных соседей в следующий уровень Li+1, а непосредственная проверка этих соседей откладывалась до перехода к обработке уровня Li+1. С другой стороны, алгоритм DFS действует более «импульсивно»: при проверке узла u он перебирает соседей u, пока не найдет первый непроверенный узел v (если он есть), после чего немедленно переключается на проверку v.

Чтобы реализовать стратегию проверки DFS, мы сначала добавляем все узлы, смежные с u, в список рассматриваемых узлов, но после этого переходим к про- верке v — нового соседа u. В процессе проверки v соседи v последовательно добав- ляются в хранимый список, но добавление происходит в порядке стека, так что эти соседи будут проверены до возвращения к проверке других соседей u. К другим узлам, смежным с u, алгоритм возвращается только тогда, когда не останется иных узлов.

Также в этой реализации используется массив Explored, аналогичный масси- ву Discovered из реализации BFS. Различие заключается в том, что Explored[v] присваивается значение true только после перебора ребер, инцидентных v (когда поиск DFS находится в точке v), тогда как алгоритм BFS присваивает Discovered[v] значение true при первом обнаружении v. Полная реализация приведена ниже.

DFS(s):

Инициализировать S как стек с одним элементом s

Пока стек S не пуст Получить узел u из S Если Explored[u]=false

Присвоить Explored[u]=true

Для  каждого  ребра  (u,  v),  инцидентного  u

Добавить v в стек S

Конец цикла Конец Если

Осталось упомянуть об одном последнем недочете: процедура поиска в глубину недостаточно четко определена, потому что список смежности проверяемого узла может обрабатываться в любом порядке. Так как приведенный выше алгоритм за- носит все смежные узлы в стек до их рассмотрения, он фактически обрабатывает каждый список смежности в порядке, обратном порядку рекурсивной версии DFS из предыдущего раздела.