http://i.stack.imgur.com/sEJKz.png
На изображении показан график. Это правильный обход в глубину? Или у меня совершенно неверная мысль? Мое понимание dfs дается отправной точкой, вы смотрите на все соседние узлы. Затем произвольно выберите один и рекурсивно «посетите» этот узел. Начиная с v, я выбрал узел 2, чтобы перейти к следующему. Цифры от 1 до 8 показывают путь.
Редактировать: кажется, я перепутал числа 2 и 3! Их следует поменять местами.
Изображение 2: http://i.stack.imgur.com/KdWl6.png
То, что вы показываете, является правильным возможным порядком поиска DFS. DFS посещает рекурсивно, как вы сказали, отмечая узлы, которые он уже посетил. Когда он достигает точки, в которой он не может рекурсивно вернуться к непосещенному узлу, он будет возвращаться до тех пор, пока не будет такой точки или поиск не завершится, поскольку все узлы помечены как посещенные.
В вашем случае он посещает 1, 2 и 3. В 3 он возвращается к 2, затем переходит к 4, 5, 6, 7, 8. Затем он возвращается, но посещаются все узлы, поэтому поиск заканчивается этим порядок посещения.
Узел, отмеченный 3 в этом случае, также мог быть 2 или 8. Например, DFS мог уйти (используя метки на вашем рисунке): 1, 2, 4, 5, 6, 7, 8, вернуться к 2, 3, прекратить.
