Backtracking используется при прохождении в глубину каждый раз, когда вы попадаете в «тупик». Это гарантирует, что каждый путь в конечном счете изучен. Например, скажем, учитывая этот график, вы выполняете обход в глубину, начиная с A. (Мы будем использовать соглашение, которое оставило потомков go первым.)
1. A -> B (синее на изображении )
B имеет ребенка! Хорошо, мы будем go там.
2. B -> D (зеленый на картинке )
D имеет 2 детей! Хорошо, давайте go оставим первым.
3. D -> E (фиолетовый на картинке )
Э-э, у детей нет детей! Это тупик. Это означает, что нам нужно вернуть назад на один уровень (go вернуться назад на D) и посмотреть, есть ли у нас другие пути, которые мы можем искать.
Да - у D еще один неисследованный ребенок. Давайте go там.
4. D -> F (розовый на картинке )
F не имеет детей! Это еще один тупик, давайте вернемся на один уровень («до» D) и посмотрим, есть ли у нас другие пути для поиска.
Нет - у Д не осталось детей. Давайте вернемся на другой уровень («вверх» до B).
Нет - детей B не осталось. Давайте откат другой уровень.
Да - у А есть еще один неисследованный ребенок! Давайте go там.
5. A -> C (желтый на рисунке )
C не имеет детей. Давайте возврат другой уровень.
Нет - у А нет детей для исследования, и это root. Это означает, что наш обход завершен! :)