Изменения

'''Обход в глубину''' (поиск в глубину, англ. ''Depth-First Search'', ''DFS'') - — один из основных методов обхода [[Основные определения теории графов|графа]], часто используемый для [[Использование обхода в глубину для проверки связности|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки|топологической сортировки]].

Общая идея алгоритма состоит в следующем: для каждой ''не пройденной'' [[Основные определения теории графов|вершины ]] необходимо найти все ''не пройденные'' [[Основные определения теории графов|смежные вершины ]] и повторить поиск для них.

#Выбираем любую вершину из еще ''не пройденных'', обозначим ее как <tex>u</tex>.#Запускаем процедуру DFS<tex>\mathrm{dfs(u)}</tex>#*Помечаем вершину <tex>u </tex> как ''пройденную''#*Для каждой ''не пройденной'' смежной с <tex>u </tex> вершиной (назовем ее <tex>v</tex>) запускаем DFS<tex>\mathrm{dfs(v)}</tex>#Повторяем шаги 1 и 2, пока все вершины не окажутся ''пройденными''.

vectorВ массиве <booltex> \mathrm{visited; []}<//вектор для хранения информации tex> хранится информация о ''пройденных'' и ''не пройденных'' вершинах.  '''function''' doDfs(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе </font> visited = array[n, ''false''] <font color=darkgreen> // создаём массив посещённых вершины длины n, заполненный ''false'' изначально</font> '''function''' dfs(u: '''int'''): visited[u] = ''true'' '''for''' v: (u, v) '''in''' G '''if''' '''not''' visited[v] dfs(v)

void dfs(int u) { visited[u] '''for''' i = true; //помечаем вершину как пройденную1 '''to''' n for (v таких, что (u, v) - ребро в G) //проходим по смежным с u вершинам '''if (!''' '''not''' visited[vi]) //проверяем, не находились ли мы ранее в выбранной вершине dfs(vi); } === Время работы === int main() Оценим время работы обхода в глубину. Процедура <tex>\mathrm{ ... dfs}<//задание графа G с количеством вершин n. visited.assign(ntex> вызывается от каждой вершины не более одного раза, false); //в начале а внутри процедуры рассматриваются все вершины в графе ''не пройденные'' for такие [[Основные определения теории графов|ребра]] <tex>\{e\ |\ \mathrm{begin(int i e)} = 0; i u\}< n; ++i) //проходим по всем вершинам графаtex>... if Всего таких ребер для всех вершин в графе <tex>O(!visited[i]E) <//...не забыв проверитьtex>, следовательно, были мы уже в очередной вершине или нет dfsвремя работы алгоритма оценивается как <tex>O(iV+E); return 0; }</tex>.

Зачастую, простой информации "были/не были в вершине" не хватает для конкретных целей.<br />  Поэтому в процессе алгоритма вершинам задают некоторые цвета:<br />:*если вершина ''белая'', значит, мы в ней еще не были, вершина ''не пройдена'';<br />:*''серая'' - — вершина ''проходится'' в текущей процедуре DFS;<br tex>\mathrm{dfs}</tex>;:*''черная'' - — вершина ''пройдена'', все итерации DFS <tex>\mathrm{dfs}</tex> от нее завершены.<br />

Отличие реализации с цветами от предыдущей лишь в массиве <tex>\mathrm{visited[]}</tex>, который мы назовем теперь <tex>\mathrm{color, и дополнительной ''черной'' "метки"[]}</tex>. При этом цвета В нем будет хранится информация о цветах вершин будут заданы следующим образом: ''белый'' - 0, ''серый'' - 1, ''черный'' - 2. Все отличия помечены '''жирным''' шрифтом.

vector<'''intfunction'''> doDfs(G[n]: '''colorGraph'''; ):<font color=darkgreen> //функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе </вектор для хранения информации font> color = array[n, ''white''] '''о цветеfunction''' вершин void dfs(u: '''int u) { '''): color[u] = 1; //раскрашиваем вершину в ''серыйgray'' цвет ''' for (''' v таких, что : (u, v) - ребро в '''in''' G) //проходим по смежным с u вершинам '''if (!''' color[v]) //проверяем, не находились ли мы ранее в выбранной вершине, == '''условие не требует изменений,'white'' dfs(v); color[u] = ''black'' '''for''' i = 1 '''to''' n '''if''' color[i] == ''white'' dfs(i) === Пример ===Рассмотрим, как будут изменяться цвета вершин при обходе в глубину данного графа. {| style="background-color:#CCC;margin:0.5px;width:600px"!style="background-color:#EEE"| Описание шага!style="background-color:#EEE"| Состояние графа|-|style="background-color:#FFF;padding:2px 10px"| В функции <tex>\mathrm{doDfs}</tex> присваиваем всем вершинам в массиве <tex>\mathrm{color[]}</поскольку мы считаем tex> белый цвет. Затем проверяем, что первая вершина окрашена в белый цвет. Заходим в нее и раскрашиваем ее в серый цвет.|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs1.png‎|150px|]]|-|style="background-color:#FFF;padding:2px 10px"| Пробуем пойти в вершину с номером 2. Проверяем, что она белая, и переходим в нее. Окрашиваем ее в серый цвет.|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs2.png‎|150px|]]|-|style="background-color:#FFF;padding:2px 10px"| Пробуем пойти в вершину с номером 3. Проверяем, что она белая, и переходим в нее. Окрашиваем ее в серый цвет.|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs3.png‎|150px|]]|-|style="background-color:#FFF;padding:2px 10px"| Проверяем, что из вершины с номером 3 не пройденнойисходит ни одного ребра. Помечаем ее в черный цвет и возвращаемся в вершину с номером 2.|style="background-color:#FFF;padding:2px 10px" только тогда| [[Файл:dfs4.png‎|150px|]]|-|style="background-color:#FFF;padding:2px 10px"| Пробуем пойти в вершину с номером 4. Проверяем, когда что она белая, и переходим в нее. Окрашиваем ее в серый цвет.|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs5_6_7.png‎|150px|]]|-|style="background-color:#FFF;padding:2px 10px"| Пробуем пойти в вершину с номером 3. Видим, что она ''белого'' черного цвета, ти остаемся на месте.е|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs5_6_7. когда png‎|150px|]]|-|style="background-color:#FFF;padding:2px 10px"| Пробуем пойти в вершину с номером 1. Видим, что она серого цвета, и остаемся на месте.|style="background-color:#FFF;padding:2px 10px"| [v[Файл:dfs5_6_7.png‎|150px|]] |-|style= 0'''"background-color:#FFF;padding:2px 10px"| Из вершины с номером 4 больше нет исходящих ребер. Помечаем ее в черный цвет и возвращаемся в вершину с номером 2. '''|style="background-color:#FFF;padding:2px 10px"| [[uФайл:dfs8.png‎|150px|]] |-|style= "background-color:#FFF;padding:2px 10px"| Из вершины с номером 2больше нет исходящих ребер. Помечаем ее в черный цвет и возвращаемся в вершину с номером 1.|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs9.png‎|150px|]]|-|style="background-color:#FFF; padding:2px 10px"| Из вершины с номером 1 больше нет исходящих ребер. Помечаем ее в черный цвет и выходим в программу <tex>\mathrm{doDfs}<//раскрашиваем вершину tex>. В ней проверяем, что все вершины окрашены в ''черный'' цвет'''. Выходим из функции <tex>\mathrm{doDfs}</tex>. Алгоритм завершен.|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs10.png‎|150px|]] |} int main== Дерево обхода в глубину ==[[Image: Colors.png|thumb|240px|Типы ребер, определяемые деревом обхода:<br>1) ребра дерева<br>2) <font color=#3771c8>обратные</font> ребра<br>3) <font color=#71c837>прямые</font> ребра<br>4) <font color=#ff2a2a>перекрестные</font> ребра]] Рассмотрим подграф предшествования обхода в глубину <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 с количеством вершин n.</tex>: * ''Ребрами дерева'color' назовем те ребра из <tex>G</tex>, которые вошли в <tex>G_p</tex>.assign* Ребра <tex>(nu, 0v);''' </tex>, соединяющие вершину <tex>u</tex> с её предком <tex>v</tex> в начале все вершины дереве обхода в графе глубину назовем ''не пройденныеобратными ребрами'', (для неориентированного графа предок должен быть ''не родителем''т.е, так как иначе ребро будет являться ребром дерева). * Ребра <tex>(u, v)</tex>, не являющиеся ребрами дерева и соединяющие вершину <tex>u</tex> с её потомком <tex>v</tex> в дереве обхода в глубину назовем ''белыепрямыми ребрами''(в неориентированном графе нет разницы между прямыми и обратными ребрами, поэтому все такие ребра считаются обратными).* Все остальные ребра назовем ''перекрестными ребрами'' — такие ребра могут соединять вершины одного и того же дерева обхода в глубину, когда ни одна из вершин не является предком другой, или соединять вершины в разных деревьях. for Алгоритм <tex>\mathrm{dfs}</tex> можно модифицировать так, что он будет классифицировать встречающиеся при работе ребра. Ключевая идея состоит в том, что каждое ребро <tex>(int i = 0; i u, v)</tex> можно классифицировать при помощи цвета вершины <tex>v< n; ++i) /tex> при первом его исследовании, а именно:* Белый цвет вершины <tex>v</проходим tex> по всем вершинам графа..определению <tex>\mathrm{dfs}</tex> говорит о том, что это ''ребро дерева''. if * Серый цвет в силу того, что серые вершины всегда образуют нисходящий путь в каком-либо из деревьев <tex>\mathrm{dfs}</tex> и встреченная вершина <tex>v</tex> лежит на нем выше вершины <tex>u</tex>, определяет ''обратное ребро'' (!visitedдля неориентированного графа необходимо проверить условие <tex>v \neq p[iu]</tex>) //...не забыв проверить* Черный цвет, соответственно, были мы уже в очередной вершине указывает на ''прямое'' или нет''перекрестное ребро''. dfs(i); return 0;== См. также == }* [[Обход в ширину]]

== Источники информации ==*[http://ru.wikipedia.org/wiki/Поиск_в_глубину Обход Википедия {{---}} Поиск в глубину на ru]*[http://en.wikipedia.org/wiki/Depth-first_search Wikipedia {{---}} Depth-first search]