172
правки
Изменения
Нет описания правки
'''Обход в глубину''' (поиск в глубину, англ. '''Depth-First Search''', '''DFS''') - один из основных методов обхода графа, часто используемый для [[Использование обхода в глубину для проверки связности|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки|топологической сортировки]].
== Алгоритм ==
=== Пошаговое представление ===
#Выбираем любую вершину из еще ''не пройденных'', обозначим ее как u.
#Запускаем процедуру DFS<tex>dfs(u)</tex>
#*Помечаем вершину u как ''пройденную''
#*Для каждой ''не пройденной'' смежной с <tex>u </tex> вершиной (назовем ее <tex>v</tex>) запускаем DFS<tex>dfs(v)</tex>
#Повторяем шаги 1 и 2, пока все вершины не окажутся ''пройденными''.
Поэтому в процессе алгоритма вершинам задают некоторые цвета:<br />
:если вершина ''белая'', значит, мы в ней еще не были, вершина ''не пройдена'';<br />
:''серая'' - вершина ''проходится'' в текущей процедуре DFS<tex>dfs</tex>;<br />:''черная'' - вершина ''пройдена'', все итерации DFS <tex>dfs</tex> от нее завершены.<br />
Такие "метки" в основном используются при [[Использование обхода в глубину для поиска цикла в ориентированном графе|поиске цикла]].
