DFS递归与DFS迭代

Question

我正在尝试理解DFS递归和DFS迭代之间的区别。使用堆栈的方法使用迭代还是递归方法？

例如，使用DFS递归遍历图形和DFS迭代遍历图形的输出是什么？按照字母顺序遍历邻居。

图表如下：

​

​

对于DFS遍历(有堆栈的那个，不确定它是递归的还是迭代的)，这是我得到的: A，C，D，E，F。谁能确认这是什么类型的DFS遍历，以及另一个是如何工作的？谢谢!

Answer 1

据我所知，递归和迭代版本仅在堆栈的使用上有所不同。递归版本使用调用堆栈，而迭代版本执行完全相同的步骤，但使用用户定义的堆栈而不是调用堆栈。步骤本身的顺序没有区别(如果使用了适当的打破平局的规则来确保子节点的相同遍历顺序-如果需要的话)，因此不可能检查输出以确定使用的是迭代实现还是递归实现。

Answer 2

正如在另一个答案中指出的，使用DFS遍历您的图将以相同的方式访问顶点，而不管实际的DFS实现是使用迭代还是递归。请参阅Wikipedia article上的伪代码。

你还有一个额外的需求，那就是按字母顺序访问相邻的顶点。这两种实现的行为将完全相同。

给定字母顺序约束，结果A、C、D、E、F是图的唯一可能的DFS遍历。