Изменения

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

vectorВ массиве <booltex> visited; []<//вектор для хранения информации tex> хранится информация о ''пройденных'' и ''не пройденных'' вершинах. void '''function''' dfs(u: '''int u''') : { visited[u] = true; //помечаем вершину как пройденную '''for (''' v таких, что : (u, v) — ребро в '''in''' G) //проходим по смежным с u вершинам '''if (!''' '''not''' visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине dfs(v); } Вызов обхода в глубину из основной программы осуществляется так: int '''function''' main(): '''int''' { ... <font color=darkgreen>//задание графа G с количеством вершин n.</font> '''fill'''(visited.assign(n, false); //в начале все вершины в графе '''for'не пройденные'' for (int i = 0; i < 1 '''to''' n; ++i) //проходим по всем вершинам графа... '''if (!''' '''not''' visited[i]) //...не забыв проверить, были мы уже в очередной вершине или нет dfs(i); return 0; }

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

Отличие реализации с цветами от предыдущей лишь в массиве <tex>visited[]</tex>, который мы назовем теперь <tex>color[]</tex>. В нем будет хранится информация о цветах вершин.  '''function''' dfs(u: '''int'''): color[u] = ''gray'' '''for''' v: (u, v) '''in''' G '''if''' color[v] == ''white'' dfs(v) color[u] = ''black'' Вызов обхода в глубину из основной программы осуществляется так: '''function''' main(): '''int''' <font color=darkgreen>//задание графа G с количеством вершин n </font> '''fill'''(color, ''white'') '''for''' i = 1 '''to''' n '''if''' color[i] == ''white'' dfs(i) === Пример ===Рассмотрим, как будут изменяться цвета вершин при обходе в глубину данного графа.

vector<color_t> {| style="background-color:#CCC;margin:0.5px; //вектор для хранения информации о цвете вершинwidth:600px" !style="background-color:#EEE"| Описание шага void dfs(int u) !style="background-color:#EEE"| Состояние графа|- {|style="background-color:#FFF;padding:2px 10px"| Из основной программы проверяем, что первая вершина окрашена в белый цвет. Заходим в нее и раскрашиваем ее в серый цвет. |style="background-color:#FFF;padding:2px 10px"| [u[Файл:dfs1.png‎|150px|] ]|-|style= GRAY"background-color:#FFF; //раскрашиваем padding:2px 10px"| Пробуем пойти в вершину с номером 2. Проверяем, что она белая, и переходим в нее. Окрашиваем ее в ''серый'' цвет.|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs2.png‎|150px|]] for (v таких|-|style="background-color:#FFF;padding:2px 10px"| Пробуем пойти в вершину с номером 3. Проверяем, что (uона белая, v) — ребро и переходим в нее. Окрашиваем ее в G) //проходим по смежным с u вершинамсерый цвет. if (|style="background-color:#FFF;padding:2px 10px"| [v[Файл:dfs3.png‎|150px|]] |-|style== WHITE) //проверяем"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. Проверяем, условие не требует измененийчто она белая, и переходим в нее. Окрашиваем ее в серый цвет. dfs(v)|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"| [v[Файл:dfs5_6_7.png‎|150px|] ]|-|style="background-color:#FFF;padding:2px 10px"| Пробуем пойти в вершину с номером 1. Видим, что она серого цвета, и остаемся на месте.|style= WHITE "background-color:#FFF;padding:2px 10px"| [u[Файл:dfs5_6_7.png‎|150px|] ]|-|style= BLACK"background-color:#FFF; //раскрашиваем вершину padding:2px 10px"| Из вершины с номером 4 больше нет исходящих ребер. Помечаем ее в ''черный'' цвет } int main() { ... //задание графа G и возвращаемся в вершину с количеством вершин nномером 2. |style="background-color.assign(n, WHITE):#FFF; //в начале все вершины в графе ''не пройденные'', т.е. ''белые''padding:2px 10px"| [[Файл:dfs8.png‎|150px|]]|- for (int i |style= 0"background-color:#FFF; i < n; ++i) //проходим по всем вершинам графа.padding:2px 10px"| Из вершины с номером 2 больше нет исходящих ребер.Помечаем ее в черный цвет и возвращаемся в вершину с номером 1. if (|style="background-color:#FFF;padding:2px 10px"| [[iФайл:dfs9.png‎|150px|]] |-|style== WHITE) //"background-color:#FFF;padding:2px 10px"| Из вершины с номером 1 больше нет исходящих ребер.Помечаем ее в черный цвет и выходим в основную программу..не забыв проверитьИз основной программы проверяем, были мы уже что все вершины окрашены в очередной вершине или нетчерный цвет. Алгоритм завершен. dfs(i); return 0|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs10.png‎|150px|]] |}

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