272
правки
Изменения
→Дерево обхода в глубину
[[Image: Colors.png|thumb|250px|Типы ребер, определяемые деревом обхода:<br>
1) ребра дерева<br>
2) <font color=#0000DE3771c8>обратные</font> ребра<br>3) <font color=#00DE0071c837>прямые</font> ребра<br>4) <font color=#DE0000ff2a2a>перекрестные</font> ребра]]
Рассмотрим подграф предшествования обхода в глубину <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>dfs(u)\ </tex> (для вершин, от которых <tex>dfs</tex> был вызван нерекурсивно это значение соответственно равно <tex>NIL</tex>). Подграф предшествования поиска в глубину образует ''лес обхода в глубину'', который состоит из нескольких ''деревьев обхода в глубину''. С помощью полученного леса можно классифицировать ребра графа <tex>G</tex>:
