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