Поиск в глубину

Определение:

Поиск в глубину — это алгоритм, ищущий по дереву (или графу) сначала в глубину начиная с корня.

• Алгоритм идёт по дереву, переходя между уровнями по левым дочерним узлам, пока не дойдёт до самого низа.
• Завершив проход по ветви, алгоритм возвращается обратно, просматривая правые дочерние узлы этой ветви. Причём, если возможно, выбирает самые левые из узлов, расположенных справа от предыдущего маршрута.
• Завершив просмотр всей ветви, алгоритм переходит к узлу, расположенному справа от корня, и снова идёт по левым дочерним узлам до самого дна.
• Последним анализируется крайний правый узел (расположенный справа от всех своих предшественников).

Что вам нужно знать:

• Алгоритм оптимален для поиска по дереву, чья глубина превышает ширину.
• Для работы алгоритма используется стек.
• Поскольку стек является LIFO-структурой, ему не нужно отслеживать указатели узлов, поэтому потребляется меньше памяти, чем в случае с поиском в ширину.
• Когда алгоритм не может дальше идти по левой стороне, он начинает анализировать стек.

Эффективность («О» большое):

• Поиск: поиск в глубину — O(|E| + |V|).
• E — количество рёбер (граней?).
• V — количество вершин.