редактировать рецепт: Поиск в глубину

Текст:

'''Поиск в глубину'''  — один из методов обхода [[Граф (математика)|графа]]. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин. https://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Depth-first-tree.svg/390px-Depth-first-tree.svg.png == Алгоритм поиска в глубину == Пусть задан [[Граф (математика)|граф]] <math>G = (V, E)</math>, где <math>V</math> — множество вершин графа, <math>E</math> — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в ''белый'' цвет. Выполним следующие действия: # Пройдём по всем вершинам <math>v \in V</math>. #* Если вершина <math>v</math> белая, выполним для неё <code>DFS(v)</code>. Процедура DFS (параметр — вершина <math>u \in V</math>) # Перекрашиваем вершину <math>u</math> в ''серый'' цвет. # Для всякой вершины <math>w</math>, [[Словарь терминов теории графов|смежной]] с вершиной <math>u</math> и окрашенной в белый цвет, [[рекурсия|рекурсивно]] выполняем процедуру # Перекрашиваем вершину <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> и указатель на предыдущую (ту, из которой пришли). == Применение == Поиск в глубину ограниченно применяется как собственно ''поиск'', чаще всего на древовидных структурах: когда расстояние между точками малó, поиск в глубину может «плутать» где-то далеко. Зато поиск в глубину — хороший инструмент для исследования топологических свойств графов. Например: * В качестве подпрограммы в алгоритмах поиска одно- и [[алгоритм Косарайю|двусвязных]] компонент. * В [[Топологическая сортировка|топологической сортировке]]. * Для поиска [[точка сочленения графа|точек сочленения]], [[мост (теория графов)|мостов]]. * Для преобразования [[Абстрактное синтаксическое дерево|синтаксического дерева]] в строку (любую: префиксную, [[инфиксная запись|инфиксную]], [[обратная польская запись|обратную польскую]]). * В различных расчётах на графах. Например, как часть [[алгоритм Диница|алгоритма Диница]] поиска максимального потока. Поиск в глубину — естественный выбор, когда агент (человек или робот) лично ходит по лабиринту и видит то, что непосредственно рядом с ним. «Правило левой руки» (идти, ведя левой рукой по стенке) будет поиском в глубину, если лабиринт древовидный (нет кружных путей). == См. также == * [[Поиск в ширину]] [[Категория:Алгоритмы поиска]] [[Category:Scripting Tutorials]]

Записать страницу Отменить