Поиск в глубину: различия между версиями

Материал из Поле цифровой дидактики
м (1 версия импортирована)
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
[[Файл:Depth-first-tree.svg|frame|Порядок обхода [[дерево (теория графов)|дерева]] в глубину]]
'''Поиск в глубину'''  — один из методов обхода [[Граф (математика)|графа]]. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.


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


== Алгоритм поиска в глубину ==
== Алгоритм поиска в глубину ==
Строка 11: Строка 11:
Процедура DFS (параметр — вершина <math>u \in V</math>)
Процедура DFS (параметр — вершина <math>u \in V</math>)
# Перекрашиваем вершину <math>u</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> в ''чёрный'' цвет.
# Перекрашиваем вершину <math>u</math> в ''чёрный'' цвет.


Строка 46: Строка 46:


'''Третий вариант''': можно в каждой из «серых» вершин держать текущее <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}}
<!-- # Перекрашиваем вершину <math>u</math> в '''серый''' цвет.
# Для всякой вершины <math>w</math>, [[Словарь терминов теории графов|смежной]] с вершиной u и окрашенной в белый цвет, выполняем процедуру <code>DFS(w)</code>.
# Перекрашиваем вершину <math>u</math> в '''чёрный''' цвет. -->
[[Алгоритм Косарайю]] требует сортировки вершин в обратном порядке по времени выхода. Метка входа и типы рёбер нужны в алгоритмах поиска [[точка сочленения графа|точек сочленения]] и [[мост (теория графов)|мостов]]. Метки выхода в обратном порядке — [[топологическая сортировка|топологический порядок]] вершин.


== Применение ==
== Применение ==
Строка 87: Строка 63:
* [[Поиск в ширину]]
* [[Поиск в ширину]]


== Примечания ==
{{примечания}}
== Литература ==
* {{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}}
{{Алгоритмы поиска на графах}}


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

Текущая версия на 20:00, 15 декабря 2022

Поиск в глубину  — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.

390px-Depth-first-tree.svg.png

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

Пусть задан граф [math]\displaystyle{ G = (V, E) }[/math], где [math]\displaystyle{ V }[/math] — множество вершин графа, [math]\displaystyle{ E }[/math] — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

  1. Пройдём по всем вершинам [math]\displaystyle{ v \in V }[/math].
    • Если вершина [math]\displaystyle{ v }[/math] белая, выполним для неё DFS(v).

Процедура DFS (параметр — вершина [math]\displaystyle{ u \in V }[/math])

  1. Перекрашиваем вершину [math]\displaystyle{ u }[/math] в серый цвет.
  2. Для всякой вершины [math]\displaystyle{ w }[/math], смежной с вершиной [math]\displaystyle{ u }[/math] и окрашенной в белый цвет, рекурсивно выполняем процедуру
  3. Перекрашиваем вершину [math]\displaystyle{ u }[/math] в чёрный цвет.

Часто используют двухцветные метки — без серого, на 1-м шаге красят сразу в чёрный цвет.

Нерекурсивные варианты

На больших графах поиск в глубину серьёзно нагружает стек вызовов. Если есть риск переполнения стека, используют нерекурсивные варианты поиска.

Первый вариант, простейший, но дающий немалый объём стека — до |E|.

  1. Кладём на стек первую вершину.
  2. Пока стек не пуст, берём верхнюю вершину, не извлекая.
    1. Если вершина белая…
      1. Красим в серый цвет.
      2. Кладём в стек всех её белых соседок в порядке, обратном порядку обхода (если таковой важен).
    2. Если вершина серая, красим в чёрный и извлекаем.
    3. Если вершина чёрная, просто извлекаем.

Если хватает двухцветных меток…

  1. Кладём на стек первую вершину.
  2. Пока стек не пуст, извлекаем верхнюю вершину. Если она белая…
    1. Красим в чёрный цвет.
    2. Кладём в стек всех её белых соседок в порядке, обратном порядку обхода.

Второй вариант: можно симулировать стек вызова программно: для каждой из серых вершин в стеке будет храниться её номер [math]\displaystyle{ u }[/math] и номер текущей смежной вершины [math]\displaystyle{ w }[/math].

Процедура DFS (параметр — вершина [math]\displaystyle{ u \in V }[/math])

  1. Кладём на стек пару [math]\displaystyle{ (u, \varnothing) }[/math]. Перекрашиваем вершину [math]\displaystyle{ u }[/math] в серый цвет.
  2. Пока стек не пуст…
    1. Берём верхнюю пару [math]\displaystyle{ (v, w) }[/math], не извлекая её из стека.
    2. Находим вершину [math]\displaystyle{ w' }[/math], смежную с [math]\displaystyle{ v }[/math] и следующую за [math]\displaystyle{ w }[/math].
      1. Если таковой нет, извлекаем [math]\displaystyle{ (v, w) }[/math] из стека, перекрашиваем вершину [math]\displaystyle{ v }[/math] в чёрный цвет.
      2. В противном случае присваиваем [math]\displaystyle{ w := w' }[/math], прямо в стеке.
        • Если к тому же вершина [math]\displaystyle{ w' }[/math] белая, кладём на стек пару [math]\displaystyle{ (w', \varnothing) }[/math], перекрашиваем [math]\displaystyle{ w' }[/math] в серый цвет.

Третий вариант: можно в каждой из «серых» вершин держать текущее [math]\displaystyle{ w }[/math] и указатель на предыдущую (ту, из которой пришли).

Применение

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

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

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

См. также

Источник — http://digida.mgpu.ru/index.php?title=Поиск_в_глубину&oldid=6575