Поиск в глубину

Другой естественный метод поиска узлов, достижимых из s, естественно приме- няется в ситуации, когда граф G действительно представляет собой лабиринт из взаимосвязанных комнат. Вы начинаете от s и проверяете первое ребро, ведущее из него, — допустим, к узлу v.
Далее вы следуете по первому ребру, выходящему из v, и продолжаете действовать по этой схеме, пока не окажетесь в «тупике» — узле, для которого вы уже исследовали всех соседей. В таком случае вы возвращаетесь к узлу, у которого имеется непроверенный сосед, и продолжаете от него. Этот ал- горитм называется алгоритмом поиска в глубину (DFS, Depth-First Search), потому что он продвигается по G на максимально возможную глубину и отступает только по мере необходимости.

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

DFS(и):

Пометить узел и как «проверенный» и добавить и в R

Для каждого ребра (и, v), инцидентного и Если узел v не помечен как «проверенный»

Рекурсивно вызвать DFS(v)

Конец Если

Конец цикла

Чтобы применить его для решения задачи связности s-t, достаточно изначально объявить все узлы «непроверенными» и вызвать DFS(s).

Между алгоритмами DFS и BFS существуют как фундаментальное сходство, так и фундаментальные отличия. Сходство основано на том факте, что оба алго- ритма строят компоненту связности, содержащую s, и, как будет показано в сле- дующем разделе, в обоих случаях достигаются сходные уровни эффективности.

Хотя алгоритм DFS в конечном итоге посещает точно те же узлы, что и BFS, обычно посещение происходит в совершенно ином порядке; поиск в глубину проходит по длинным путям и может заходить очень далеко от s, прежде чем вернуться к более близким непроверенным вариантам. Это различие проявляется в том факте, что алгоритм DFS, как и BFS, строит естественное корневое дерево T из компоненты, содержащей s, но обычно такое дерево имеет совершенно иную структуру. Узел s становится корнем дерева T, а узел и становится родителем v, если и отвечает за обнаружение v. А именно, если DFS(v) вызывается непосред- ственно во время вызова DFS(и), ребро (и, v) добавляется в T. Полученное дерево называется деревом поиска в глубину компоненты R.

На рис. 3.5 изображен процесс построения дерева DFS с корнем в узле 1 для графа на рис. 3.2. Сплошными линиями обозначены ребра T, а пунктирными — ре- бра G, не принадлежащие T. Выполнение алгоритма DFS начинается с построения пути, содержащего узлы 1, 2, 3, 5, 4. Выполнение заходит в тупик в узле 4, в котором найти новые узлы не удается, поэтому алгоритм возвращается к узлу 5, находит узел 6, снова возвращается к 4 и находит узлы 7 и 8. В этой точке в компоненте связности новых узлов нет, поэтому все незавершенные рекурсивные вызовы DFS завершаются один за другим, а выполнение подходит к концу. Полное дерево DFS изображено на рис. 3.5, g.


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

Чтобы обосновать это утверждение, следует отметить следующее свойство ал- горитма DFS и дерева, которое он строит.

(3.6) Для заданного рекурсивного вызова DFS(u) все узлы, помеченные как «про- веренные» между вызовом и концом рекурсивного вызова, являются потомками и в T.

Используя (3.6), мы докажем следующее утверждение:

(3.7) Пусть T — дерево поиска в глубину, x и у — узлы T, а (x, у) — ребро G, которое не является ребром T. В этом случае один из узлов — x или у — является предком другого.

Доказательство. Предположим, (x, у) — ребро G, которое не является ребром T, и без потери общности будем считать, что узел x первым обнаруживается алгорит- мом DFS. При проверке ребра (x,у) в ходе выполнения DFS(x) оно не добавляется в T, потому что узел у помечен как «проверенный». Так как узел у не был помечен как «проверенный» при изначальном вызове DFS(x), этот узел был обнаружен между вызовом и концом рекурсивного вызова DFS(x). Из (3.6) следует, что у является потомком x. ■

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

Еще по теме Поиск в глубину:

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