Изменения

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

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

Оценим время работы обхода в глубину. Процедура <tex>dfs</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[Основные определения теории графов|ребра ]] <tex>\{e\ |\ begin(e) = u\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>.