最近，我需要实现非递归DFS作为更复杂的算法（准确地说，是Tarjan算法）的一部分。递归实现非常优雅，但不适用于大型图。当我实现迭代版本时，我对它最终变得多么精致感到震惊，我想知道自己做错了什么。
迭代DFS有两种基本方法。首先，您可以一次将一个节点的所有子节点推入堆栈（似乎更为常见）。或者，您也可以按一个。我将专注于第一个，因为每个人似乎都是这样做的。
我在使用此算法时遇到各种问题，最终我意识到要高效地执行该操作，我不需要1，而不是2，而是3个布尔值（我不一定表示您需要三个显式的布尔变量，您可以存储通过特殊的变量值（通常是整数）间接获取信息，但您需要以一种或另一种方式访问这3条信息，这三个标志分别是：1）已访问。这是为了防止将孩子过多地推入堆栈。 2）完成。防止对同一节点进行冗余处理。 3）升/降。指示孩子是否已经被推入堆栈。伪代码如下所示：
while(S)
if S.peek().done == True
S.pop()
continue
S.peek().visited = True
if S.peek().descending == True
S.peek().descending = False
for c in S.peek().children
if c.visited == False
S.push(c)
doDescendingStuff()
else
w = S.pop()
w.done = True
doAscendingStuff()
一些注意事项：1）您不需要技术上的升序/降序，因为您可以看到孩子是否全部完成。但是在密集图中它效率很低。
2），主要的作用：似乎没有必要访问/完成操作。这就是为什么（我认为）您需要它。在堆栈上访问它们之前，您不能标记访问过的事物。如果这样做，则可能以错误的顺序处理事物。例如。假设A链接到B和C，B链接到D，D链接到C。然后从A，将B和C压入堆栈。从B您将D压入堆栈...然后呢？如果您在将访问的事物压入堆栈时标记了访问的事物，则此处不会将C压入堆栈。但这是错误的，此图中的C应该从D访问，而不是从A访问（假设A在C之前访问B）。因此，在处理之前，您不会标记访问过的事物。但是随后，您将在堆栈上两次获得C。因此，您需要另一个标志来表明您已完全完成它，因此您无需再次处理C。
我看不出如何避免所有这些事情，而拥有一个完全正确的非递归DFS，该DFS支持收尾动作。但是本能地感觉很脆弱。有没有更好的办法？我在网上咨询的几乎每个地方都真正掩盖了如何实际实现非递归DFS，并说可以做到这一点并提供一个非常基本的算法。当算法正确时（就正确地支持到同一节点的多条路径而言），这种情况很少见，它很少正确地支持在绕线和展开时进行操作。
我认为最优雅的基于堆栈的实现将在堆栈上具有子代迭代器，而不是节点。可以将迭代器视为在其子节点中存储节点和位置。
while (!S.empty)
Iterator i = S.pop()
bool found = false
Iterator temp = null
while (i.hasNext())
Node n = i.next()
if (n.visited == false)
n.visited = true
doDescendingStuff(n)
temp = n.getChildrenIterator()
break
if (!i.hasNext())
doAscendingStuff(i.getNode())
else
S.push(i)
if (temp != null)
S.push(temp)
以上可以通过将节点和位置分离到2个堆栈上来优化i.t.o存储空间。
您的代码没有完全模仿递归DFS实现的情况。在递归DFS实现中，每个节点在任何时候在堆栈中仅出现一次。
Dukeling提供的解决方案是一种迭代方式。基本上，您一次只需要推送一个节点，而不是一次推送全部。]
您断言这将需要更多存储的说法是错误的：在您的实现中，一个节点可以在堆栈上多次。实际上，如果您从非常密集的图形（所有顶点上的完整图形）开始，则会发生这种情况。使用Dukeling解决方案，堆栈的大小为O（顶点数）。在您的解决方案中，它是O（边数）。
算法BFS（G，v）
Robert Sedgewick在cpp书中的算法讨论了一种特殊的堆栈，该堆栈仅保留一个项目的一个副本，而忘记了旧副本。不能完全确定如何执行此操作，但是可以消除堆栈中有多个项目的问题。
Tl; dr是您不需要多个标志。
这里是到Java程序的链接，该Java程序同时显示了递归和非递归方法的DFS，并且还计算了discovery
为了使用堆栈进行DFS遍历，请从堆栈中弹出一个节点（记住将初始节点压入堆栈中，并检查是否已被访问。如果已经访问过，则忽略然后弹出，否则输出弹出节点，将其标记为已访问并将其所有邻居推入堆栈。继续这样做，直到堆栈为空。