Алгоритм обхода в глубину (DFS) позволяет проверить, является ли одна вершина дерева предком другой. 5

Принцип работы: начиная с некоторой вершины, алгоритм идёт по рёбрам графа, пока не упрётся в тупик. 1 Вершина называется тупиком, если в ней нет исходящих рёбер, ведущих в непосещённые вершины. 1

После попадания в тупик алгоритм возвращается назад вдоль пройденного пути, пока не обнаружит вершину, у которой есть исходящие рёбра, ведущие в непосещённые вершины. 1 Затем он идёт по одному из таких рёбер. 1

Процесс заканчивается, когда алгоритм возвращается в начальную вершину, а все соседние вершины уже оказались посещёнными. 1

Если после этого остаются непосещённые вершины, то алгоритм повторяет поиск из одной из них. 1 Так происходит до тех пор, пока не будут обнаружены все вершины графа. 15

Вершина является предком другой, когда вторая вершина была обнаружена во время вызова алгоритма из первой. 2 В этом случае отрезок обработки второй вершины вложен в отрезок обработки первой. 2