Русская Википедия:Поиск в глубину
Поиск в глубину (Шаблон:Lang-en) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершинШаблон:Sfn.
Алгоритм поиска в глубину
Пусть задан граф <math>G = (V, E)</math>, где <math>V</math> — множество вершин графа, <math>E</math> — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:
- Пройдём по всем вершинам <math>v \in V</math>.
- Если вершина <math>v</math> белая, выполним для неё
DFS(v)
.
- Если вершина <math>v</math> белая, выполним для неё
Процедура DFS (параметр — вершина <math>u \in V</math>)
- Перекрашиваем вершину <math>u</math> в серый цвет.
- Для всякой вершины <math>w</math>, смежной с вершиной <math>u</math> и окрашенной в белый цвет, рекурсивно выполняем процедуру
DFS(w)
[1]. - Перекрашиваем вершину <math>u</math> в чёрный цвет.
Часто используют двухцветные метки — без серого, на 1-м шаге красят сразу в чёрный цвет.
Нерекурсивные варианты
На больших графах поиск в глубину серьёзно нагружает стек вызовов. Если есть риск переполнения стека, используют нерекурсивные варианты поиска.
Первый вариант, простейший, но дающий немалый объём стека — до |E|.
- Кладём в стек первую вершину.
- Пока стек не пуст, берём верхнюю вершину, не извлекая.
- Если вершина белая…
- Красим в серый цвет.
- Кладём в стек всех её белых соседок в порядке, обратном порядку обхода (если таковой важен).
- Если вершина серая, красим в чёрный и извлекаем.
- Если вершина чёрная, просто извлекаем.
- Если вершина белая…
Если хватает двухцветных меток…
- Кладём в стек первую вершину.
- Пока стек не пуст, извлекаем верхнюю вершину. Если она белая…
- Красим в чёрный цвет.
- Кладём в стек всех её белых соседок в порядке, обратном порядку обхода.
Второй вариант: можно представить стек вызова программно: для каждой из серых вершин в стеке будет храниться её номер <math>u</math> и номер текущей смежной вершины <math>w</math>.
Процедура DFS (параметр — вершина <math>u \in V</math>)
- Кладём в стек пару <math>(u, \varnothing)</math>. Перекрашиваем вершину <math>u</math> в серый цвет.
- Пока стек не пуст…
- Берём верхнюю пару <math>(v, w)</math>, не извлекая её из стека.
- Находим вершину <math>w'</math>, смежную с <math>v</math> и следующую за <math>w</math>.
- Если таковой нет, извлекаем <math>(v, w)</math> из стека, перекрашиваем вершину <math>v</math> в чёрный цвет.
- В противном случае присваиваем <math>w := w'</math>, прямо в стеке.
- Если к тому же вершина <math>w'</math> белая, кладём на стек пару <math>(w', \varnothing)</math>, перекрашиваем <math>w'</math> в серый цвет.
Третий вариант: можно в каждой из «серых» вершин держать текущее <math>w</math> и указатель на предыдущую (ту, из которой пришли).
Поиск в глубину с метками времени. Классификация рёбер
Для каждой из вершин установим два числа — «время» входа <math>entry[u]</math> и «время» выхода <math>leave[u]</math>.
Модифицируем процедуру DFS так.
- Увеличиваем «текущее время» на 1. <math>entry[u] := t</math>.
- Перекрашиваем вершину <math>u</math> в серый цвет.
- Для всякой вершины <math>v</math>, смежной с вершиной <math>u</math> и окрашенной в белый цвет, выполняем процедуру
DFS(v)
. - Перекрашиваем вершину <math>u</math> в чёрный цвет.
- Увеличиваем «текущее время» на 1. <math>leave[u] := t</math>.
Считаем, что граф ориентированный. Очевидно, для любой вершины, из которой мы не вышли в момент t, <math>entry[u] \leqslant t < leave[u]</math>. Также невозможно скрёстное неравенство: <math>entry[u] < entry[v] < leave[u] < leave[v]</math>. Просматриваемые на шаге 3 дуги u→v могут быть:
- <math>entry[u] < t + 1 = entry[v] < leave[v] < leave[u]</math>. В момент выполнения шага 3 (обозначенный как t) вершина v белая. В таком случае мы для вершины v исполняем DFS, а дуга называется дугой дерева поиска.
- <math>entry[u] < entry[v] < leave[v] \leqslant t < leave[u]</math>. В момент t вершина v чёрная, сравнение entry говорит, что в v попали из u. Такая дуга называется прямой.
- <math>entry[v] < leave[v] < entry[u] \leqslant t < leave[u]</math>. В момент t вершина v также чёрная, но сравнение entry говорит, что в v попали в обход u. Такая дуга называется перекрёстной.
- <math>entry[v] < entry[u] \leqslant t < leave[u] < leave[v]</math>. В момент t вершина v серая, то есть в u попали из v. Имеем дело с обратной дугой.
Рёбра неориентированного графа могут быть рёбрами дерева и обратными, но не прямыми и перекрёстными.[2] Чтобы различать рёбра неориентированного графа, достаточно указанных выше трёх- или двухцветных отметок. Ребро, идущее в белую вершину,— ребро дерева. В серую (чёрную в двухцветном варианте) — обратное. В чёрную — такого не бывает.Шаблон:Sfn
Алгоритм Косарайю требует сортировки вершин в обратном порядке по времени выхода. Метка входа и типы рёбер нужны в алгоритмах поиска точек сочленения и мостов. Метки выхода в обратном порядке — топологический порядок вершин.
Применение
Поиск в глубину ограниченно применяется как собственно поиск, чаще всего на древовидных структурах: когда расстояние между точками малó, поиск в глубину может «плутать» где-то далеко.
Зато поиск в глубину — хороший инструмент для исследования топологических свойств графов. Например:
- В качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент.
- В топологической сортировке.
- Для поиска точек сочленения, мостов.
- Для преобразования синтаксического дерева в строку (любую: префиксную, инфиксную, обратную польскую).
- В различных расчётах на графах. Например, как часть алгоритма Диница поиска максимального потока.
Поиск в глубину — естественный выбор, когда агент (человек или робот) лично ходит по лабиринту и видит то, что непосредственно рядом с ним. «Правило левой руки» (идти, ведя левой рукой по стенке) будет поиском в глубину, если лабиринт древовидный (нет кружных путей).
См. также
Примечания
Литература
Ссылки
- ВКИ НГУ: Методы программирования. Обходы графа.
- СпбГУ ИТМО, Факультет информационных технологий и программирования: Дискретная математика. Алгоритмы. Обход графа в глубину.
- Реализация поиска в глубину и различные задачи, решаемые с его помощью (сайт e-maxx.ru)
- Поиск в глубину
- Обход в глубину, цвета вершин — Викиконспекты ИТМО
Шаблон:Rq Шаблон:Алгоритмы поиска на графах
- ↑ Шаблон:Cite web
- ↑ Если в сторону u→v оно прямое, то ранее его прошли в сторону v→u как обратное. Если в сторону u→v оно перекрёстное, его должны были пройти v→u как ребро дерева.