Изменения
Нет описания правки
'''Обход в глубину''' (поиск в глубину, англ. '''Depth-First Search''', '''DFS''') - — один из основных методов обхода [[Основные определения теории графов|графа]], часто используемый для [[Использование обхода в глубину для проверки связности|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки|топологической сортировки]].
== Алгоритм ==
{
visited[u] = true; //помечаем вершину как пройденную
for (v таких, что (u, v) - — ребро в G) //проходим по смежным с u вершинам
if (!visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине
dfs(v);
Поэтому в процессе алгоритма вершинам задают некоторые цвета:<br />
:если вершина ''белая'', значит, мы в ней еще не были, вершина ''не пройдена'';<br />
:''серая'' - — вершина ''проходится'' в текущей процедуре <tex>dfs</tex>;<br />:''черная'' - — вершина ''пройдена'', все итерации <tex>dfs</tex> от нее завершены.<br />
Такие "метки" в основном используются при [[Использование обхода в глубину для поиска цикла в ориентированном графе|поиске цикла]].
=== Реализация ===
Отличие реализации с цветами от предыдущей лишь в массиве visited, который мы назовем теперь color. При этом цвета вершин будут заданы следующим образом: ''белый'' - — 0, ''серый'' - — 1, ''черный'' - — 2.
vector<int> color; //вектор для хранения информации о цвете вершин
{
color[u] = 1; //раскрашиваем вершину в ''серый'' цвет
for (v таких, что (u, v) - — ребро в G) //проходим по смежным с u вершинам
if (!color[v]) //проверяем, не находились ли мы ранее в выбранной вершине, условие не требует изменений,
dfs(v); //поскольку мы считаем вершину "не пройденной" только тогда, когда она ''белого'' цвета, т.е. когда color[v] = 0
