Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Поиск в глубину (depth-first search) как метод обхода графа - понятие, примеры кратко

Лекция



Привет, сегодня поговорим про поиск в глубину, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое поиск в глубину, depth-first search, обход графа , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

поиск в глубину (англ. depth-first search , DFS) — один из методов обхода графа. Стратегия поиска в глубину, как следует из ее названия, состоит в том, чтобы идти "вглубь" графа, насколько это возможно. При выполнении поиска в глубину исследуются все ребра, выходящие из вершины, открытой последней, и покидает вершину, только когда не остается неисследованных ребер — при этом происходит возврат в вершину, из которой была открыта вершина v. Этот процесс продолжается до тех пор, пока не будут открыты все вершины, достижимые из исходной. Если при этом остаются неоткрытые вершины, то одна из них выбирается в качестве новой исходной вершины и поиск повторяется уже из нее. Этот процесс повторяется до тех пор, пока не будут открыты все вершины.

Когда вершина v открывается в процессе сканирования списка смежности уже открытой вершины и, процедура поиска записывает это событие, устанавливая поле предшественника v prev[v] равным u. В отличие от поиска в ширину, где подграф предшествования образует дерево, при поиске в глубинуподграф предшествования может состоять из нескольких деревьев, так как поиск может выполняться из нескольких исходных вершин.

Как и в процессе выполнения поиска в ширину, вершины графа раскрашиваются в разные цвета, свидетельствующие о их состоянии. Каждая вершина изначально белая, затем при открытии (discover) в процессе поиска она окрашивается в серый цвет, и по завершении (finish), когда ее список смежности полностью сканирован, она становится черной. Такая методика гарантирует, что каждая вершина в конечном счете находится только в одном дереве поиска в глубину.

Помимо построения леса поиска в глубину, поиск в глубину также проставляет в вершинах метки времени (timestamp). Каждая вершина имеет две такие метки — первую d [v], в которой указывается, когда вершина у открывается (и окрашивается в серый цвет), и вторая — f[v], которая фиксирует момент, когда поиск завершает сканирование списка смежности вершины у и она становится черной. Эти метки используются многими алгоритмами и полезны при рассмотрении поведения поиска в глубину.

Формальное описание

 Поиск в глубину (depth-first search) как метод обхода графа - понятие, примеры

 Поиск в глубину (depth-first search) как метод обхода графа - понятие, примеры

В строках 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]| раз. Поскольку
Поиск в глубину (depth-first search) как метод обхода графа - понятие, примеры
общая стоимость выполнения строк 4-7 процедуры DFS_Visit равна o(Е).

Время работы процедуры DFS, таким образом, равно o(V + Е).

Пример

Порядок обхода дерева в глубину:

Поиск в глубину (depth-first search) как метод обхода графа - понятие, примеры

Граф и остовное дерево, полученное при обходе его вершин методом поиска в глубину:
Поиск в глубину (depth-first search) как метод обхода графа - понятие, примеры

Поиск в глубину (англ. depth-first search, DFS) – это рекурсивный алгоритм обхода вершин графа. Если метод поиска в ширину производился симметрично (вершины графа просматривались по уровням), то данный метод предполагает продвижение вглубь до тех пор, пока это возможно. Невозможность дальнейшего продвижения, означает, что следующим шагом будет переход на последний, имеющий несколько вариантов движения (один из которых исследован полностью), ранее посещенный узел (вершина). Отсутствие последнего свидетельствует об одной из двух возможных ситуаций: либо все вершины графа уже просмотрены, либо просмотрены все те, что доступны из вершины, взятой в качестве начальной, но не все (несвязные и ориентированные графы допускают последний вариант).

Рассмотрим то, как будет вести себя алгоритм на конкретном примере. Приведенный далее неориентированный связный граф имеет в сумме 5 вершин.Поиск в глубину (depth-first search) как метод обхода графа - понятие, примеры

Сначала необходимо выбрать начальную вершину. Какая бы вершина в качестве таковой не была выбрана, граф в любом случае исследуется полностью, поскольку, как уже было сказано, это связный граф без единого направленного ребра.
Пусть обход начнется с узла 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) и вершина с тем же номером, что и проверяемый столбец матрицы при этом не была посещена, то функция рекурсивно повторяется. В противном случае функция возвращается на предыдущую стадию рекурсии.

Код программы на C++:

Поиск в глубину (depth-first search) как метод обхода графа - понятие, примеры

Код программы на Pascal:

Поиск в глубину (depth-first search) как метод обхода графа - понятие, примеры

Для простоты понимания результата, выдаваемого двумя программами, взят неориентированный граф, приводимый ранее в качестве примера, и представленный матрицей смежности graph .

Применение

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

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

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

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

Вау!! 😲 Ты еще не читал? Это зря!

На этом все! Теперь вы знаете все про поиск в глубину, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое поиск в глубину, depth-first search, обход графа и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов

создано: 2014-10-13
обновлено: 2021-12-15
132596



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Алгоритмы и теория алгоритмов

Термины: Алгоритмы и теория алгоритмов