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

Поиск в глубину  — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.

Алгоритм поиска в глубину

Пусть задан граф [math]\displaystyle{ G = (V, E) }[/math], где [math]\displaystyle{ V }[/math] — множество вершин графа, [math]\displaystyle{ E }[/math] — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

1. Пройдём по всем вершинам [math]\displaystyle{ v \in V }[/math].
   • Если вершина [math]\displaystyle{ v }[/math] белая, выполним для неё DFS(v).

Процедура DFS (параметр — вершина [math]\displaystyle{ u \in V }[/math])

1. Перекрашиваем вершину [math]\displaystyle{ u }[/math] в серый цвет.
2. Для всякой вершины [math]\displaystyle{ w }[/math], смежной с вершиной [math]\displaystyle{ u }[/math] и окрашенной в белый цвет, рекурсивно выполняем процедуру
3. Перекрашиваем вершину [math]\displaystyle{ u }[/math] в чёрный цвет.

Часто используют двухцветные метки — без серого, на 1-м шаге красят сразу в чёрный цвет.

Нерекурсивные варианты

На больших графах поиск в глубину серьёзно нагружает стек вызовов. Если есть риск переполнения стека, используют нерекурсивные варианты поиска.

Первый вариант, простейший, но дающий немалый объём стека — до |E|.

1. Кладём на стек первую вершину.
2. Пока стек не пуст, берём верхнюю вершину, не извлекая.
   1. Если вершина белая…
      1. Красим в серый цвет.
      2. Кладём в стек всех её белых соседок в порядке, обратном порядку обхода (если таковой важен).
   2. Если вершина серая, красим в чёрный и извлекаем.
   3. Если вершина чёрная, просто извлекаем.

Если хватает двухцветных меток…

1. Кладём на стек первую вершину.
2. Пока стек не пуст, извлекаем верхнюю вершину. Если она белая…
   1. Красим в чёрный цвет.
   2. Кладём в стек всех её белых соседок в порядке, обратном порядку обхода.

Второй вариант: можно симулировать стек вызова программно: для каждой из серых вершин в стеке будет храниться её номер [math]\displaystyle{ u }[/math] и номер текущей смежной вершины [math]\displaystyle{ w }[/math].

Процедура DFS (параметр — вершина [math]\displaystyle{ u \in V }[/math])

1. Кладём на стек пару [math]\displaystyle{ (u, \varnothing) }[/math]. Перекрашиваем вершину [math]\displaystyle{ u }[/math] в серый цвет.
2. Пока стек не пуст…
   1. Берём верхнюю пару [math]\displaystyle{ (v, w) }[/math], не извлекая её из стека.
   2. Находим вершину [math]\displaystyle{ w' }[/math], смежную с [math]\displaystyle{ v }[/math] и следующую за [math]\displaystyle{ w }[/math].
      1. Если таковой нет, извлекаем [math]\displaystyle{ (v, w) }[/math] из стека, перекрашиваем вершину [math]\displaystyle{ v }[/math] в чёрный цвет.
      2. В противном случае присваиваем [math]\displaystyle{ w := w' }[/math], прямо в стеке.
         • Если к тому же вершина [math]\displaystyle{ w' }[/math] белая, кладём на стек пару [math]\displaystyle{ (w', \varnothing) }[/math], перекрашиваем [math]\displaystyle{ w' }[/math] в серый цвет.

Третий вариант: можно в каждой из «серых» вершин держать текущее [math]\displaystyle{ w }[/math] и указатель на предыдущую (ту, из которой пришли).

Применение

Поиск в глубину ограниченно применяется как собственно поиск, чаще всего на древовидных структурах: когда расстояние между точками малó, поиск в глубину может «плутать» где-то далеко.

Зато поиск в глубину — хороший инструмент для исследования топологических свойств графов. Например:

• В качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент.
• В топологической сортировке.
• Для поиска точек сочленения, мостов.
• Для преобразования синтаксического дерева в строку (любую: префиксную, инфиксную, обратную польскую).
• В различных расчётах на графах. Например, как часть алгоритма Диница поиска максимального потока.

Поиск в глубину — естественный выбор, когда агент (человек или робот) лично ходит по лабиринту и видит то, что непосредственно рядом с ним. «Правило левой руки» (идти, ведя левой рукой по стенке) будет поиском в глубину, если лабиринт древовидный (нет кружных путей).

См. также

• Поиск в ширину