Изменения

#Запускаем процедуру <tex>\mathrm{dfs(u)}</tex>

#*Для каждой ''не пройденной'' смежной с <tex>u</tex> вершиной (назовем ее <tex>v</tex>) запускаем <tex>\mathrm{dfs(v)}</tex>

В массиве <tex>\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) Вызов обхода в глубину из основной программы осуществляется так: '''function''' main(): '''int''' <font color=darkgreen>//задание графа G с количеством вершин n </font> '''fill'''(visited, false)

'''if''' '''not''' visited[i] dfs(i)

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

*''серая'' — вершина ''проходится'' в текущей процедуре <tex>\mathrm{dfs}</tex>;*''черная'' — вершина ''пройдена'', все итерации <tex>\mathrm{dfs}</tex> от нее завершены.

Отличие реализации с цветами от предыдущей лишь в массиве <tex>\mathrm{visited[]}</tex>, который мы назовем теперь <tex>\mathrm{color[]}</tex>. В нем будет хранится информация о цветах вершин.

'''function''' doDfs(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе </font> color = array[n, ''white''] '''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'')

'''if''' color[i] == ''white'' dfs(i)

|style="background-color:#FFF;padding:2px 10px"| Из основной программы В функции <tex>\mathrm{doDfs}</tex> присваиваем всем вершинам в массиве <tex>\mathrm{color[]}</tex> белый цвет. Затем проверяем, что первая вершина окрашена в белый цвет. Заходим в нее и раскрашиваем ее в серый цвет.

|style="background-color:#FFF;padding:2px 10px"| Из вершины с номером 1 больше нет исходящих ребер. Помечаем ее в черный цвет и выходим в основную программу<tex>\mathrm{doDfs}</tex>. Из основной программы В ней проверяем, что все вершины окрашены в черный цвет. Выходим из функции <tex>\mathrm{doDfs}</tex>. Алгоритм завершен.

Рассмотрим подграф предшествования обхода в глубину <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</tex>:

Алгоритм <tex>\mathrm{dfs}</tex> можно модифицировать так, что он будет классифицировать встречающиеся при работе ребра. Ключевая идея состоит в том, что каждое ребро <tex>(u, v)</tex> можно классифицировать при помощи цвета вершины <tex>v</tex> при первом его исследовании, а именно:* Белый цвет вершины <tex>v</tex> по определению <tex>\mathrm{dfs}</tex> говорит о том, что это ''ребро дерева''.* Серый цвет в силу того, что серые вершины всегда образуют нисходящий путь в каком-либо из деревьев <tex>\mathrm{dfs}</tex> и встреченная вершина <tex>v</tex> лежит на нем выше вершины <tex>u</tex>, определяет ''обратное ребро'' (для неориентированного графа необходимо проверить условие <tex>v \neq p[u]</tex>).