Изменения
→Реализация
'''Обход в глубину''' (поиск в глубину, англ. '''Depth-First Search''', '''DFS''') - — один из основных методов обхода [[Основные определения теории графов|графа]], часто используемый для [[Использование обхода в глубину для проверки связности|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки|топологической сортировки]].
== Алгоритм ==
=== Общая идея ===
Общая идея алгоритма состоит в следующем: для каждой ''не пройденной'' [[Основные определения теории графов|вершины ]] необходимо найти все ''не пройденные'' [[Основные определения теории графов|смежные вершины ]] и повторить поиск для них.
=== Пошаговое представление ===
#Выбираем любую вершину из еще ''не пройденных'', обозначим ее как <tex>u</tex>.#Запускаем процедуру <tex>\mathrm{dfs(u)}</tex>#*Помечаем вершину <tex>u </tex> как ''пройденную''#*Для каждой ''не пройденной'' смежной с <tex>u</tex> вершиной (назовем ее <tex>v</tex>) запускаем <tex>\mathrm{dfs(v)}</tex>#Повторяем шаги 1 и 2, пока все вершины не окажутся ''пройденными''.
=== Реализация ===
=== Время работы ===
Оценим время работы обхода в глубину. Процедура <tex>\mathrm{dfs}</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[Основные определения теории графов|ребра ]] <tex>\{e\ |\ \mathrm{begin(e) } = u\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>.
== Цвета вершин ==
Зачастую, простой информации "были/не были в вершине" не хватает для конкретных целей.<br /> Поэтому в процессе алгоритма вершинам задают некоторые цвета:<br />:*если вершина ''белая'', значит, мы в ней еще не были, вершина ''не пройдена'';<br />:*''серая'' - — вершина ''проходится'' в текущей процедуре <tex>\mathrm{dfs}</tex>;<br />:*''черная'' - — вершина ''пройдена'', все итерации <tex>\mathrm{dfs}</tex> от нее завершены.<br />
Такие "метки" в основном используются при [[Использование обхода в глубину для поиска цикла в ориентированном графе|поиске цикла]].
=== Реализация ===
Отличие реализации с цветами от предыдущей лишь в массиве <tex>\mathrm{visited[]}</tex>, который мы назовем теперь <tex>\mathrm{color, и дополнительной ''черной'' "метки"[]}</tex>. При этом цвета В нем будет хранится информация о цветах вершин будут заданы следующим образом: ''белый'' - 0, ''серый'' - 1, ''черный'' - 2.
== Дерево обхода в глубину ==
[[Image:tree_edgesColors.png|thumb|270px240px|Типы ребер, определяемые деревом обхода]]Рассмотрим подграф предшествования обхода в глубину <tex>G_p = (V, E_p)</tex>, где <tex>E_p = \{(p[u], u) : u \in V,\ p[u] \neq NIL\}</tex>, где в свою очередь <tex>p[u]</tex> — вершина, от которой был вызван <tex>dfs(u)\ </tex> (для вершин, от которых <tex>dfs</tex> был вызван нерекурсивно это значение соответственно равно <tex>NIL</texbr>1). Подграф предшествования поиска в глубину образует лес обхода в глубину, который состоит из нескольких деревьев обхода в глубину. Назовем '''ребрами дерева''' те ребра из <tex>G</tex>, которые вошли в <tex>G_p</tex>. Рассмотрим такие ребра графа <tex>G</tex>, которые не попали в <tex>G_p</tex>. Ребра <tex>(u, v)</tex>, соединяющие вершину <tex>u</tex> с её предком <tex>v</tex> в дереве обхода в глубину назовем '''обратными ребрами'''. Ребра <tex>(u, v)</tex>, не являющиеся ребрами дерева и соединяющие вершину <texbr>u</tex> с её потомком <tex>v</tex> в дереве обхода в глубину назовем '''прямыми ребрами'''. Все остальные ребра назовем '''перекрестными ребрами''' — такие ребра могут соединять вершины одного и того же дерева обхода в глубину, когда ни одна из вершин не является предком другой, или соединять вершины в разных деревьях.Алгоритм 2) <texfont color=#3771c8>dfsобратные</texfont> можно модифицировать так, что он будет классифицировать встречающиеся при работе ребра. Ключевая идея состоит в том, что каждое ребро <texbr>(u, v3)</texfont color=#71c837> можно классифицировать при помощи цвета вершины <tex>vпрямые</texfont> при первом его исследовании, а именно:* Белый цвет вершины <tex>v</tex> по определению ребра<texbr>dfs</tex> говорит о том, что это ребро дерева.* Серый цвет в силу того, что серые вершины всегда образуют нисходящий путь в каком-либо из деревьев 4) <texfont color=#ff2a2a>dfsперекрестные</texfont> и встреченная вершина <tex>v</tex> лежит на нем выше вершины <tex>u</tex>, определяет обратное ребро.* Черный цвет, соответственно, указывает на прямое или перекрестное ребро.ребра]]
Рассмотрим подграф предшествования обхода в глубину <tex>G_p = (V, E_p)</tex>, где <tex>E_p = \{(p[u], u) : u \in V,\ p[u] \neq NIL\}</tex>, где в свою очередь <tex>p[u]</tex> — вершина, от которой был вызван <tex>\mathrm{dfs(u)}\ </tex> (для вершин, от которых <tex>\mathrm{dfs}</tex> был вызван нерекурсивно это значение соответственно равно <tex>NIL</tex>). Подграф предшествования поиска в глубину образует ''лес обхода в глубину'', который состоит из нескольких ''деревьев обхода в глубину''. С помощью полученного леса можно классифицировать ребра графа <tex>G</tex>:* ''Ребрами дерева'' назовем те ребра из <tex>G</tex>, которые вошли в <tex>G_p</tex>. * Ребра <tex>(u, v)</tex>, соединяющие вершину <tex>u</tex> с её предком <tex>v</tex> в дереве обхода в глубину назовем ''обратными ребрами'' (для неориентированного графа предок должен быть ''не родителем'', так как иначе ребро будет являться ребром дерева). * Ребра <tex>(u, v)</tex>, не являющиеся ребрами дерева и соединяющие вершину <tex>u</tex> с её потомком <tex>v</tex> в дереве обхода в глубину назовем ''прямыми ребрами'' (в неориентированном графе нет разницы между прямыми и обратными ребрами, поэтому все такие ребра считаются обратными). * Все остальные ребра назовем ''перекрестными ребрами'' — такие ребра могут соединять вершины одного и того же дерева обхода в глубину, когда ни одна из вершин не является предком другой, или соединять вершины в разных деревьях.Алгоритм <tex>\mathrm{dfs}</tex> можно модифицировать так, что он будет классифицировать встречающиеся при работе ребра. Ключевая идея состоит в том, что каждое ребро <tex>(u, v)</tex> можно классифицировать при помощи цвета вершины <tex>v</tex> при первом его исследовании, а именно:* Белый цвет вершины <tex>v</tex> по определению <tex>\mathrm{dfs}</tex> говорит о том, что это ''ребро дерева''.* Серый цвет в силу того, что серые вершины всегда образуют нисходящий путь в каком-либо из деревьев <tex>\mathrm{dfs}</tex> и встреченная вершина <tex>v</tex> лежит на нем выше вершины <tex>u</tex>, определяет ''обратное ребро'' (для неориентированного графа необходимо проверить условие <tex>v \neq p[u]</tex>).* Черный цвет, соответственно, указывает на ''прямое'' или ''перекрестное ребро''. == См. также ==* [[Обход в ширину]] == Источники информации ==*[http://ru.wikipedia.org/wiki/Поиск_в_глубину Обход Википедия {{---}} Поиск в глубину на ru]*[http://en.wikipedia.org/wiki/Depth-first_search Wikipedia {{---}} Depth-first search]
*[http://www.e-maxx.ru/algo/dfs Обход в глубину. Реализации.]
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, второе издание. Пер. с англ. — Издательский дом "Вильямс", 2007. — 1296 с. — Глава 22. Элементарные алгоритмы для работы с графами.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]