Открыть главное меню
Порядок обхода дерева в глубину

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

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

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

  1. Пройдём по всем вершинам  .
    • Если вершина   белая, выполним для неё DFS(v).

Процедура DFS (параметр — вершина  )

  1. Перекрашиваем вершину   в серый цвет.
  2. Для всякой вершины  , смежной с вершиной   и окрашенной в белый цвет, рекурсивно выполняем процедуру DFS(w)[2].
  3. Перекрашиваем вершину   в чёрный цвет.

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

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

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

Первый вариант: можно симулировать стек вызова программно: для каждой из серых вершин в стеке будет храниться её номер   и номер текущей смежной вершины  .

Процедура DFS (параметр — вершина  )

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

Второй вариант: можно в каждой из «серых» вершин держать текущее   и указатель на предыдущую (ту, из которой пришли).

Третий вариант работает, если хватает двухцветных меток.

Процедура DFS (параметр — вершина  )

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

Поиск в глубину с метками времени. Классификация рёберПравить

 
Поиск в глубину с метками времени. Порядок выбора рёбер — слева направо.

Для каждой из вершин установим два числа — «время» входа   и «время» выхода  .

Модифицируем процедуру DFS так.

  1. Увеличиваем «текущее время» на 1.  .
  2. Перекрашиваем вершину   в серый цвет.
  3. Для всякой вершины  , смежной с вершиной   и окрашенной в белый цвет, выполняем процедуру DFS(v).
  4. Перекрашиваем вершину   в чёрный цвет.
  5. Увеличиваем «текущее время» на 1.  .

Считаем, что граф ориентированный. Очевидно, для любой вершины, из которой мы не вышли в момент t,  . Также невозможно скрёстное неравенство:  . Просматриваемые на шаге 3 дуги uv могут быть:

  •  . В момент выполнения шага 3 (обозначенный как t) вершина v белая. В таком случае мы для вершины v исполняем DFS, а дуга называется дугой дерева поиска.
  •  . В момент t вершина v чёрная, сравнение entry говорит, что в v попали из u. Такая дуга называется прямой.
  •  . В момент t вершина v также чёрная, но сравнение entry говорит, что в v попали в обход u. Такая дуга называется перекрёстной.
  •  . В момент t вершина v серая, то есть в u попали из v. Имеем дело с обратной дугой.

Рёбра неориентированного графа могут быть рёбрами дерева и обратными, но не прямыми и перекрёстными.[3] Чтобы различать рёбра неориентированного графа, достаточно указанных выше трёх- или двухцветных отметок. Ребро, идущее в белую вершину,— ребро дерева. В серую (чёрную в двухцветном варианте) — обратное. В чёрную — такого не бывает.[4]

Алгоритм Косарайю требует сортировки вершин в обратном порядке по времени выхода. Метка входа и типы рёбер нужны в алгоритмах поиска точек сочленения и мостов.

ПрименениеПравить

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

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

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

См. такжеПравить

ПримечанияПравить

  1. Cormen, 2005, p. 622.
  2. Обход в глубину, цвета вершин — Викиконспекты
  3. Если в сторону u→v оно прямое, то ранее его прошли в сторону v→u как обратное. Если в сторону u→v оно перекрёстное, его должны были пройти v→u как ребро дерева.
  4. Cormen, 2005, с. 628—629.

ЛитератураПравить

СсылкиПравить