depth-first-search - 在深度优先遍历中如何使用回溯？

每次遇到“死胡同”时，都会在深度优先遍历中使用回溯。它确保最终探索每条路径。例如，假设给定这张图，您从 A 开始进行深度优先遍历。（我们将使用让孩子先走的约定。）

1. A -> B（图中蓝色）

B有一个孩子！很好，我们会去那里。

2. B -> D（图中绿色）

D有2个孩子！很好，我们先向左走。

3. D -> E（图中紫色）

哦哦，E没有孩子！这是一个死胡同。这意味着我们需要回溯一个级别（返回“向上”到 D），看看我们是否还有其他可以搜索的路径。

是的——D 有另一个未开发的孩子。让我们去那里。

4. D -> F（图中粉红色）

F没有孩子！这是另一个死胡同，让我们回溯一个级别（“向上”到 D），看看我们是否还有其他路径可以搜索。

否 - D 没有孩子。让我们回溯另一个级别（“向上”到 B）。

否 - B 没有孩子。让我们回溯另一个层次。

是的——A还有一个未开发的孩子！让我们去那里。

5. A -> C（图中黄色）

C 没有孩子。让我们回溯另一个层次。

不——A 没有孩子可以探索，它是根。这意味着我们的遍历完成了！:)