DFS遍历迭代

Question

我正在尝试理解DFS递归和DFS迭代之间的区别。在这个问题中，邻居按字母顺序迭代。

使用DFS递归，我得到A，C，D，E，F。然而，我不理解DFS迭代遍历的过程。我的教授说，使用DFS迭代方法，应该得到A、E、D、C、F。有人能给我指引正确的方向吗？

如下图所示：

​

Answer 1

对于一个图，可以有一种以上的方法来使用DFS遍历节点，并从相同的源开始。举个例子，把你的图表示成一个邻接表。它可以是：

B: A
A: C, D, E
C: D, E, F
F: D

或

B: A
A: E, D, C
C: F, D, E
F: D

两者都是有效的表示。但是如果你按照它们在邻居列表中出现的顺序选择尾巴来实现它，第一个将导致: A->C->D->E->F，而第二个将导致A->E->D->C->F。这两个都是有效的遍历。

Answer 2

在运行时间方面，两者大致相同。

如果有什么不同的话，那就是使用迭代式DFS应该会稍微快一点，因为只要有递归函数返回，堆栈帧就不必返回。

为了回答你的问题，你的递归DFS没有使用堆栈，而你的迭代DFS使用堆栈。因此，您的递归DFS将查看所有邻居，如果尚未找到邻居，则立即执行DFS。这就是顺序是A、C、D、..等的原因。对于您的迭代DFS，它利用了一个堆栈，因此将首先遍历最后存储的节点。因为我们是按字母顺序排列的，所以E将存储在最后，所以它将首先从A开始遍历，然后是D、C，依此类推。