Лекция
Привет, сегодня поговорим про поиск в глубину, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое поиск в глубину, depth-first search, обход графа , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.
поиск в глубину (англ. depth-first search , DFS) — один из методов обхода графа. Стратегия поиска в глубину, как следует из ее названия, состоит в том, чтобы идти "вглубь" графа, насколько это возможно. При выполнении поиска в глубину исследуются все ребра, выходящие из вершины, открытой последней, и покидает вершину, только когда не остается неисследованных ребер — при этом происходит возврат в вершину, из которой была открыта вершина v. Этот процесс продолжается до тех пор, пока не будут открыты все вершины, достижимые из исходной. Если при этом остаются неоткрытые вершины, то одна из них выбирается в качестве новой исходной вершины и поиск повторяется уже из нее. Этот процесс повторяется до тех пор, пока не будут открыты все вершины.
Когда вершина v открывается в процессе сканирования списка смежности уже открытой вершины и, процедура поиска записывает это событие, устанавливая поле предшественника v prev[v] равным u. В отличие от поиска в ширину, где подграф предшествования образует дерево, при поиске в глубинуподграф предшествования может состоять из нескольких деревьев, так как поиск может выполняться из нескольких исходных вершин.
Как и в процессе выполнения поиска в ширину, вершины графа раскрашиваются в разные цвета, свидетельствующие о их состоянии. Каждая вершина изначально белая, затем при открытии (discover) в процессе поиска она окрашивается в серый цвет, и по завершении (finish), когда ее список смежности полностью сканирован, она становится черной. Такая методика гарантирует, что каждая вершина в конечном счете находится только в одном дереве поиска в глубину.
Помимо построения леса поиска в глубину, поиск в глубину также проставляет в вершинах метки времени (timestamp). Каждая вершина имеет две такие метки — первую d [v], в которой указывается, когда вершина у открывается (и окрашивается в серый цвет), и вторая — f[v], которая фиксирует момент, когда поиск завершает сканирование списка смежности вершины у и она становится черной. Эти метки используются многими алгоритмами и полезны при рассмотрении поведения поиска в глубину.
В строках 1-3 все вершины окрашиваются в белый цвет, а их поля тг инициализируются значением nil. В строке 4 выполняется сброс глобального счетчика времени. В строках 5-7 поочередно проверяются все вершины из V, и когда обнаруживается белая вершина, она обрабатывается при помощи процедуры DFS_Visit. Каждый раз при вызове процедуры DFS_Visit(u) в строке 7, вершина и становится корнем нового дерева леса поиска в глубину. При возврате из процедуры DFS каждой вершине и сопоставляются два момента времени — время открытия (discovery time) d [u] и время завершения (finishing time) f[u].
При каждом вызове DFS_Visit(ix) вершина и изначально имеет белый цвет. Об этом говорит сайт https://intellect.icu . В строке 1 она окрашивается в серый цвет, в строке 2 увеличивается глобальная переменная time, а в строке 3 выполняется запись нового значения переменной time в поле времени открытия d [u]. В строках 4-7 исследуются все вершины, смежные с u, и выполняется рекурсивное посещение белых вершин. При рассмотрении в строке 4 вершины v є Adj [и], мы говорим, что ребро (u, v) исследуется (explored) поиском в глубину. И наконец, после того как будут исследованы все ребра, покидающие u, в строках 8-9 вершина и окрашивается в черный цвет, а в поле f[u] записывается время завершения работы с ней.
Циклы в строках 1-3 и 5-7 процедуры DFS выполняются за время o(V), исключая время, необходимое для вызова процедуры DFS_Visit. Процедура DFS_VISIT вызывается ровно по одному разу для каждой вершины v є V, так как она вызывается только для белых вершин, и первое, что она делает, — это окрашивает переданную в качестве параметра вершину в серый цвет. В процессе выполнения DFS_Visit(v) цикл в строках 4-7 выполняется |Adj [v]| раз. Поскольку
общая стоимость выполнения строк 4-7 процедуры DFS_Visit равна o(Е).
Время работы процедуры DFS, таким образом, равно o(V + Е).
Порядок обхода дерева в глубину:
Граф и остовное дерево, полученное при обходе его вершин методом поиска в глубину:
Поиск в глубину (англ. depth-first search, DFS) – это рекурсивный алгоритм обхода вершин графа. Если метод поиска в ширину производился симметрично (вершины графа просматривались по уровням), то данный метод предполагает продвижение вглубь до тех пор, пока это возможно. Невозможность дальнейшего продвижения, означает, что следующим шагом будет переход на последний, имеющий несколько вариантов движения (один из которых исследован полностью), ранее посещенный узел (вершина). Отсутствие последнего свидетельствует об одной из двух возможных ситуаций: либо все вершины графа уже просмотрены, либо просмотрены все те, что доступны из вершины, взятой в качестве начальной, но не все (несвязные и ориентированные графы допускают последний вариант).
Рассмотрим то, как будет вести себя алгоритм на конкретном примере. Приведенный далее неориентированный связный граф имеет в сумме 5 вершин.
Сначала необходимо выбрать начальную вершину. Какая бы вершина в качестве таковой не была выбрана, граф в любом случае исследуется полностью, поскольку, как уже было сказано, это связный граф без единого направленного ребра.
Пусть обход начнется с узла 1, тогда порядок последовательности просмотренных узлов будет следующим: 1 2 3 5 4. Если выполнение начать, например, с узла 3, то порядок обхода окажется иным: 3 2 1 5 4.
Алгоритм поиска в глубину базируется на рекурсии, т. е. функция обхода, по мере выполнения, вызывает сама себя, что делает код в целом довольно компактным. Псевдокод алгоритма:
Заголовок функции DFS(st)
Вывести (st)
visited[st] ← посещена;
Для r=1 до n выполнять
Если (graph[st, r] ≠ 0) и (visited[r] не посещена) то DFS(r)
Здесь DFS (depth-firstsearch) – название функции. Единственный ее параметр st – стартовый узел, передаваемый из главной части программы как аргумент. Каждому из элементов логического массива visited заранее присваивается значение false, т. е. каждая из вершин изначально будет значиться как не посещенная. Двумерный массив graph – это матрица смежности графа. Большую часть внимания следует сконцентрировать на последней строке. Если элемент матрицы смежности, на каком то шаге равен 1 (а не 0) и вершина с тем же номером, что и проверяемый столбец матрицы при этом не была посещена, то функция рекурсивно повторяется. В противном случае функция возвращается на предыдущую стадию рекурсии.
Для простоты понимания результата, выдаваемого двумя программами, взят неориентированный граф, приводимый ранее в качестве примера, и представленный матрицей смежности graph .
Поиск в глубину ограниченно применяется как собственно поиск, чаще всего на древовидных структурах: когда расстояние между точками малó, поиск в глубину может «плутать» где-то далеко.
Зато поиск в глубину — хороший инструмент для исследования топологических свойств графов. Например:
Поиск в глубину — естественный выбор, когда агент (человек или робот) лично ходит по лабиринту и видит то, что непосредственно рядом с ним. «Правило левой руки» (идти, ведя левой рукой по стенке) будет поиском в глубину, если лабиринт древовидный (нет кружных путей).
Алгоритмы поиска на графах
|
|
---|---|
Неинформированные методы |
|
Информированные методы |
|
Кратчайшие пути |
|
Минимальное остовное дерево | |
Другое |
|
На этом все! Теперь вы знаете все про поиск в глубину, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое поиск в глубину, depth-first search, обход графа и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов
Комментарии
Оставить комментарий
Алгоритмы и теория алгоритмов
Термины: Алгоритмы и теория алгоритмов