Поиск в глубину - История изменений

Patarakin в 17:00, 15 декабря 2022

2022-12-15T17:00:51Z

← Предыдущая версия		Версия от 20:00, 15 декабря 2022
Строка 65:		Строка 65:

	[[Категория:Алгоритмы поиска]]		[[Категория:Алгоритмы поиска]]
			[[Category:Scripting Tutorials]]

Patarakin в 08:19, 20 октября 2022

2022-10-20T08:19:44Z

← Предыдущая версия		Версия от 11:19, 20 октября 2022
Строка 1:		Строка 1:
	'''Поиск в глубину''' — один из методов обхода [[Граф (математика)\|графа]]. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.		'''Поиск в глубину''' — один из методов обхода [[Граф (математика)\|графа]]. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.

			https://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Depth-first-tree.svg/390px-Depth-first-tree.svg.png

	== Алгоритм поиска в глубину ==		== Алгоритм поиска в глубину ==

Patarakin в 18:11, 19 октября 2022

2022-10-19T18:11:47Z

@@ Строка 1: / Строка 1: @@
-[[Файл:Depth-first-tree.svg|frame|Порядок обхода [[дерево (теория графов)|дерева]] в глубину]]
+'''Поиск в глубину'''  — один из методов обхода [[Граф (математика)|графа]]. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.
 == Алгоритм поиска в глубину ==
@@ Строка 11: / Строка 9: @@
 Процедура DFS (параметр — вершина <math>u \in V</math>)
 # Перекрашиваем вершину <math>u</math> в ''серый'' цвет.
-# Для всякой вершины <math>w</math>, [[Словарь терминов теории графов|смежной]] с вершиной <math>u</math> и окрашенной в белый цвет, [[рекурсия|рекурсивно]] выполняем процедуру <code>DFS(w)</code><ref>{{Cite web |url=http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83%2C_%D1%86%D0%B2%D0%B5%D1%82%D0%B0_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD |title=Обход в глубину, цвета вершин — Викиконспекты |access-date=2022-07-26 |archive-date=2022-04-02 |archive-url=https://web.archive.org/web/20220402171725/https://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83,_%D1%86%D0%B2%D0%B5%D1%82%D0%B0_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD |deadlink=no }}</ref>.
+# Для всякой вершины <math>w</math>, [[Словарь терминов теории графов|смежной]] с вершиной <math>u</math> и окрашенной в белый цвет, [[рекурсия|рекурсивно]] выполняем процедуру
 # Перекрашиваем вершину <math>u</math> в ''чёрный'' цвет.
@@ Строка 46: / Строка 44: @@
 '''Третий вариант''': можно в каждой из «серых» вершин держать текущее <math>w</math> и указатель на предыдущую (ту, из которой пришли).
 == Применение ==
@@ Строка 87: / Строка 61: @@
 * [[Поиск в ширину]]
 [[Категория:Алгоритмы поиска]]

Patarakin: 1 версия импортирована

2022-10-19T17:55:00Z

1 версия импортирована

← Предыдущая версия	Версия от 20:55, 19 октября 2022
(нет различий)

ru_wikipedia>InternetArchiveBot: Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8.8

2022-07-26T05:09:04Z

Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8.8

Новая страница

[[Файл:Depth-first-tree.svg|frame|Порядок обхода [[дерево (теория графов)|дерева]] в глубину]]

'''Поиск в глубину''' ({{lang-en|Depth-first search, '''DFS'''}}) — один из методов обхода [[Граф (математика)|графа]]. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин{{sfn|Cormen|2005|p=622}}.

== Алгоритм поиска в глубину ==
Пусть задан [[Граф (математика)|граф]] <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> и окрашенной в белый цвет, [[рекурсия|рекурсивно]] выполняем процедуру <code>DFS(w)</code><ref>{{Cite web |url=http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83%2C_%D1%86%D0%B2%D0%B5%D1%82%D0%B0_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD |title=Обход в глубину, цвета вершин — Викиконспекты |access-date=2022-07-26 |archive-date=2022-04-02 |archive-url=https://web.archive.org/web/20220402171725/https://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83,_%D1%86%D0%B2%D0%B5%D1%82%D0%B0_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD |deadlink=no }}</ref>.
# Перекрашиваем вершину <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> и указатель на предыдущую (ту, из которой пришли).

== Поиск в глубину с метками времени. Классификация рёбер ==
[[Файл:DepthFirstSearchTimestampsRu.svg|thumb|right|250px|Поиск в глубину с метками времени. Порядок выбора рёбер — слева направо.]]
Для каждой из вершин установим два числа — «время» входа <math>entry[u]</math> и «время» выхода <math>leave[u]</math>.

Модифицируем процедуру DFS так.
# Увеличиваем «текущее время» на 1. <math>entry[u] = t</math>.
# Перекрашиваем вершину <math>u</math> в серый цвет.
# Для всякой вершины <math>v</math>, [[Словарь терминов теории графов|смежной]] с вершиной <math>u</math> и окрашенной в белый цвет, выполняем процедуру <code>DFS(v)</code>.
# Перекрашиваем вершину <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''. Имеем дело с '''обратной''' дугой.

Рёбра неориентированного графа могут быть рёбрами дерева и обратными, но не прямыми и перекрёстными.<ref>Если в сторону u→v оно прямое, то ранее его прошли в сторону v→u как обратное. Если в сторону u→v оно перекрёстное, его должны были пройти v→u как ребро дерева.</ref> Чтобы различать рёбра неориентированного графа, достаточно указанных выше трёх- или двухцветных отметок. Ребро, идущее в белую вершину,— ребро дерева. В серую (чёрную в двухцветном варианте) — обратное. В чёрную — такого не бывает.{{sfn|Cormen|2005|с=628—629}}


[[Алгоритм Косарайю]] требует сортировки вершин в обратном порядке по времени выхода. Метка входа и типы рёбер нужны в алгоритмах поиска [[точка сочленения графа|точек сочленения]] и [[мост (теория графов)|мостов]]. Метки выхода в обратном порядке — [[топологическая сортировка|топологический порядок]] вершин.

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

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

* В качестве подпрограммы в алгоритмах поиска одно- и [[алгоритм Косарайю|двусвязных]] компонент.
* В [[Топологическая сортировка|топологической сортировке]].
* Для поиска [[точка сочленения графа|точек сочленения]], [[мост (теория графов)|мостов]].
* Для преобразования [[Абстрактное синтаксическое дерево|синтаксического дерева]] в строку (любую: префиксную, [[инфиксная запись|инфиксную]], [[обратная польская запись|обратную польскую]]).
* В различных расчётах на графах. Например, как часть [[алгоритм Диница|алгоритма Диница]] поиска максимального потока.

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

== См. также ==
* [[Поиск в ширину]]

== Примечания ==
{{примечания}}

== Литература ==
* {{source|Q21694522|part=Глава 5. Метод уменьшения размера задачи: Поиск в глубину|pages=212—215}}
* {{книга
|часть = Глава 22. Элементарные алгоритмы для работы с графами
|заглавие = Алгоритмы: построение и анализ(второе издание)
|автор = [[Кормен, Томас|Кормен Т.]], [[Лейзерсон, Чарльз Эрик|Лейзерсон Ч.]], [[Ривест, Рональд Линн|Ривест Р.]]
|ссылка =
|страницы = 622—632
|год = 2005
|место = М.
|издательство = [[Вильямс (издательство)|«Вильямс»]]
|ref=Cormen
}}

== Ссылки ==
{{wikibooks|Реализации алгоритмов/Поиск в глубину|Примеры реализации поиска в глубину}}
* [http://hci.fenster.name/304y/practice/lab6/ ВКИ НГУ: Методы программирования. Обходы графа.]
* [https://web.archive.org/web/20060519015128/http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-dfs-2005/algorithm СпбГУ ИТМО, Факультет информационных технологий и программирования: Дискретная математика. Алгоритмы. Обход графа в глубину.]
* [http://e-maxx.ru/algo/dfs Реализация поиска в глубину и различные задачи, решаемые с его помощью (сайт e-maxx.ru)]
* [http://kvodo.ru/dfs.html Поиск в глубину]
* [http://neerc.ifmo.ru/wiki/index.php?title=Обход_в_глубину,_цвета_вершин Обход в глубину, цвета вершин — Викиконспекты ИТМО]

{{rq|refless}}
{{Алгоритмы поиска на графах}}

[[Категория:Алгоритмы на графах]]
[[Категория:Алгоритмы поиска]]
[[Категория:Алгоритмы поиска на графах]]