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

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

По сути, рекурсивная структура DFS может рассматриваться как механизм занесения узлов в стек для последующей обработки с первоочередной обработкой последних обнаруженных узлов. А сейчас будет показано, как реализовать алгоритм DFS на базе стека узлов, ожидающих обработки.

В обоих алгоритмах, 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 из предыдущего раздела.