Поиск в глубину () — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.
Алгоритм поиска в глубину Пусть задан граф , где — множество вершин графа, — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:
Пройдём по всем вершинам . Если вершина белая, выполним для неё DFS(v).
Процедура DFS (параметр — вершина ) Перекрашиваем вершину в серый цвет. Для всякой вершины , смежной с вершиной и окрашенной в белый цвет, рекурсивно выполняем процедуру DFS(w). Перекрашиваем вершину в чёрный цвет.
Часто используют двухцветные метки — без серого, на 1-м шаге красят сразу в чёрный цвет.
Нерекурсивные варианты На больших графах поиск в глубину серьёзно нагружает стек вызовов. Если есть риск переполнения стека, используют нерекурсивные варианты поиска.
Первый вариант, простейший, но дающий немалый объём стека — до |E|. Кладём в стек первую вершину. Пока стек не пуст, берём верхнюю вершину, не извлекая. Если вершина белая… Красим в серый цвет. Кладём в стек всех её белых соседок в порядке, обратном порядку обхода (если таковой важен). Если вершина серая, красим в чёрный и извлекаем. Если вершина чёрная, просто извлекаем.
Если хватает двухцветных меток… Кладём в стек первую вершину. Пока стек не пуст, извлекаем верхнюю вершину. Если она белая… Красим в чёрный цвет. Кладём в стек всех её белых соседок в порядке, обратном порядку обхода.
Второй вариант: можно представить стек вызова программно: для каждой из серых вершин в стеке будет храниться её номер и номер текущей смежной вершины .
Процедура DFS (параметр — вершина ) Кладём в стек пару . Перекрашиваем вершину в серый цвет. Пока стек не пуст… Берём верхнюю пару , не извлекая её из стека. Находим вершину , смежную с и следующую за . Если таковой нет, извлекаем из стека, перекрашиваем вершину в чёрный цвет. В противном случае присваиваем , прямо в стеке. Если к тому же вершина белая, кладём на стек пару , перекрашиваем в серый цвет.
Третий вариант: можно в каждой из «серых» вершин держать текущее и указатель на предыдущую (ту, из которой пришли).
Поиск в глубину с метками времени. Классификация рёбер
Для каждой из вершин установим два числа — «время» входа и «время» выхода .
Модифицируем процедуру DFS так. Увеличиваем «текущее время» на 1. . Перекрашиваем вершину в серый цвет. Для всякой вершины , смежной с вершиной и окрашенной в белый цвет, выполняем процедуру DFS(v). Перекрашиваем вершину в чёрный цвет. Увеличиваем «текущее время» на 1. .
Считаем, что граф ориентированный. Очевидно, для любой вершины, из которой мы не вышли в момент t, . Также невозможно скрёстное неравенство: . Просматриваемые на шаге 3 дуги u→v могут быть: . В момент выполнения шага 3 (обозначенный как t) вершина v белая. В таком случае мы для вершины v исполняем DFS, а дуга называется дугой дерева поиска. . В момент t вершина v чёрная, сравнение entry говорит, что в v попали из u. Такая дуга называется прямой. . В момент t вершина v также чёрная, но сравнение entry говорит, что в v попали в обход u. Такая дуга называется перекрёстной. . В момент t вершина v серая, то есть в u попали из v. Имеем дело с обратной дугой.
Рёбра неориентированного графа могут быть рёбрами дерева и обратными, но не прямыми и перекрёстными.Если в сторону u→v оно прямое, то ранее его прошли в сторону v→u как обратное. Если в сторону u→v оно перекрёстное, его должны были пройти v→u как ребро дерева. Чтобы различать рёбра неориентированного графа, достаточно указанных выше трёх- или двухцветных отметок. Ребро, идущее в белую вершину,— ребро дерева. В серую (чёрную в двухцветном варианте) — обратное. В чёрную — такого не бывает.
Алгоритм Косарайю требует сортировки вершин в обратном порядке по времени выхода. Метка входа и типы рёбер нужны в алгоритмах поиска точек сочленения и мостов. Метки выхода в обратном порядке — топологический порядок вершин.
Применение Поиск в глубину ограниченно применяется как собственно поиск, чаще всего на древовидных структурах: когда расстояние между точками мало́, поиск в глубину может «плутать» где-то далеко.
Зато поиск в глубину — хороший инструмент для исследования топологических свойств графов. Например:
В качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент. В топологической сортировке. Для поиска точек сочленения, мостов. Для преобразования синтаксического дерева в строку (любую: префиксную, инфиксную, обратную польскую). В различных расчётах на графах. Например, как часть алгоритма Диница поиска максимального потока.
Поиск в глубину — естественный выбор, когда агент (человек или робот) физически ходит по лабиринту и видит то, что непосредственно рядом с ним. «Правило левой руки» (идти, ведя левой рукой по стенке) будет поиском в глубину, если лабиринт древовидный (нет кружных путей). Если же кружные пути есть, дополнительно нужна нить Ариадны: разматывать клубок и разворачиваться, когда наткнулся на свою нитку. Для экономии нитки можно сматывать её, когда идёшь назад, ведь, как сказано выше, на неориентированном графе все вершины-препятствия серые.
См. также Поиск в ширину
Примечания
Литература
Ссылки
ВКИ НГУ: Методы программирования. Обходы графа. СпбГУ ИТМО, Факультет информационных технологий и программирования: Дискретная математика. Алгоритмы. Обход графа в глубину. Реализация поиска в глубину и различные задачи, решаемые с его помощью (сайт e-maxx.ru) Поиск в глубину Обход в глубину, цвета вершин — Викиконспекты ИТМО
Категория:Алгоритмы на графах Категория:Алгоритмы поиска Категория:Алгоритмы поиска на графах