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

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

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

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

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

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

DFS(s):

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

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

Присвоить Explored[u]=true Для каждого ребра (u, v), инцидентного и Добавить v в стек S Конец цикла Конец Если

Конец Пока

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

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

(3.12) Приведенный выше алгоритм реализует поиск DFS в том смысле, что он посещает узлы точно в таком же порядке, как и рекурсивная процедура DFS из предыдущего раздела (не считая того, что списки смежности обрабатываются в обратном порядке). Если мы хотим, чтобы алгоритм также строил дерево DFS, для каждого узла и в стеке S также должна храниться информация об узле, который «привел» к включению и в стек. Задача легко решается при помощи массива parent: при каждом добавлении узла v в стек из-за ребра (u, v) выполняется присваивание parent[v] = u. Когда узел и ф s помечается как «проверенный», ребро (u,parent[u]) также можно добавить в дерево T. Учтите, что узел v может включаться в стек S многократно, поскольку он может быть смежным с несколькими проверяемыми узлами, и для каждого такого узла в стек S добавляется копия v. Однако для про- верки узла v будет использоваться только одна из этих копий — та, которая была добавлена последней. В результате для каждого узла v достаточно хранить только одно значение parent[v], просто перезаписывая значение parent[v] при каждом до- бавлении в стек S новой копии v.

Основной фазой алгоритма является добавление и удаление узлов из стека S, которое выполняется за время 0(1). Следовательно, чтобы определить границу времени выполнения, необходимо оценить количество таких операций. Чтобы подсчитать количество операций со стеком, достаточно подсчитать количество узлов, добавленных в S, так как для каждого удаления из S узел должен быть сна- чала добавлен.

Сколько элементов будет добавлено в S? Как и прежде, пусть nv — степень узла v. Узел v будет добавляться в стек S каждый раз, когда проверяется один из n его смежных узлов, так что общее количество узлов, добавленное в S, не превышает = 2т. Это доказывает искомую оценку О{т + N) для времени

выполнения DFS.

(3.13) Для графа, заданного представлением списка смежности, приведенная выше реализация алгоритма DFS выполняется за время 0(m + n) (то есть в линей- ной зависимости от размера входных данных).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Реализация поиска в глубину:

  1. 11.2.1. Область реализации права на поиск, получение и потребление информации в Интернет
  2. Поиск смысла жизни – это поиск бессмертия!
  3. ПСИХОЛОГИЯ ГЛУБИННАЯ
  4. Глава V - ГЛУБИНА
  5. 3.11.11. В глубине
  6. Глава V. ГЛУБИНА
  7. 5.1. Функции глубинного интервьюирования
  8. 5.1. ФУНКЦИИ ГЛУБИННОГО ИНТЕРВЬЮИРОВАНИЯ
  9. 2. Высота и глубина
  10. 1.1 Глубинная проблема: амбивалентность
  11. 3. Глубинная психология конфликта и странное свойство закона
  12. Растворение в глубинах организма или отпускание “туда, откуда пришло”?
  13. 10. Важно развивать духовное зрение, свое видение глубинных нравственных свойств личности ребенка
  14. Глава 6. Реализация права
  15. РЕАЛИЗАЦИЯ МЫСЛЕННОГО ПРЕДСТАВЛЕНИЯ
  16. 4.2. Реализация