Изменения

Перейти к: навигация, поиск

Обход в глубину, цвета вершин

10 байт добавлено, 14:37, 17 декабря 2016
Нет описания правки
В массиве <tex>\mathrm{visited[]}</tex> хранится информация о ''пройденных'' и ''не пройденных'' вершинах.
'''function''' doDfs(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе </font> fill(visited, ''false'')
'''function''' dfs(u: '''int'''):
visited[u] = ''true''
dfs(v)
'''fill'''(visited, ''false'')
'''for''' i = 1 '''to''' n
'''if''' '''not''' visited[i]
=== Время работы ===
Оценим время работы обхода в глубину. Процедура <tex>\mathrm{dfs}</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[Основные определения теории графов|ребра]] <tex>\{e\ |\ \mathrm{begin(e) } = u\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>.
== Цвета вершин ==
Отличие реализации с цветами от предыдущей лишь в массиве <tex>\mathrm{visited[]}</tex>, который мы назовем теперь <tex>\mathrm{color[]}</tex>. В нем будет хранится информация о цветах вершин.
'''function''' doDfs(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе </font> fill(color, ''white'')
'''function''' dfs(u: '''int'''):
color[u] = ''gray''
color[u] = ''black''
'''fill'''(color, ''white'')
'''for''' i = 1 '''to''' n
'''if''' color[i] == ''white''
60
правок

Навигация