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

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

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

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

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

Процедура DFS (параметр — вершина $u \in V$ )

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

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

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

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

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

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

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

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

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

Процедура DFS (параметр — вершина $u \in V$ )

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

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

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

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

Для каждой из вершин установим два числа — «время» входа $e n t r y [u]$ и «время» выхода $l e a v e [u]$ .

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

Увеличиваем «текущее время» на 1. $e n t r y [u] : = t$ .
Перекрашиваем вершину $u$ в серый цвет.
Для всякой вершины $v$ , смежной с вершиной $u$ и окрашенной в белый цвет, выполняем процедуру DFS(v).
Перекрашиваем вершину $u$ в чёрный цвет.
Увеличиваем «текущее время» на 1. $l e a v e [u] : = t$ .

Считаем, что граф ориентированный. Очевидно, для любой вершины, из которой мы не вышли в момент t, $e n t r y [u] ⩽ t < l e a v e [u]$ . Также невозможно скрёстное неравенство: $e n t r y [u] < e n t r y [v] < l e a v e [u] < l e a v e [v]$ . Просматриваемые на шаге 3 дуги u→v могут быть:

$e n t r y [u] < t + 1 \equiv e n t r y [v] < l e a v e [v] < l e a v e [u]$ . В момент выполнения шага 3 (обозначенный как t) вершина v белая. В таком случае мы для вершины v исполняем DFS, а дуга называется дугой дерева поиска.
$e n t r y [u] < e n t r y [v] < l e a v e [v] ⩽ t < l e a v e [u]$ . В момент t вершина v чёрная, сравнение entry говорит, что в v попали из u. Такая дуга называется прямой.
$e n t r y [v] < l e a v e [v] < e n t r y [u] ⩽ t < l e a v e [u]$ . В момент t вершина v также чёрная, но сравнение entry говорит, что в v попали в обход u. Такая дуга называется перекрёстной.
$e n t r y [v] < e n t r y [u] ⩽ t < l e a v e [u] < l e a v e [v]$ . В момент t вершина v серая, то есть в u попали из v. Имеем дело с обратной дугой.

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

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

Применение

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

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

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

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

См. также

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

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Wikibooks

Шаблон:Rq Шаблон:Алгоритмы поиска на графах

↑ Шаблон:Cite web
↑ Если в сторону u→v оно прямое, то ранее его прошли в сторону v→u как обратное. Если в сторону u→v оно перекрёстное, его должны были пройти v→u как ребро дерева.

[1] Шаблон:Cite web

[2] Если в сторону u→v оно прямое, то ранее его прошли в сторону v→u как обратное. Если в сторону u→v оно перекрёстное, его должны были пройти v→u как ребро дерева.

[1]

[2]