非递归 dfs（何时将其标记为已访问？）

Question

所以我最近实现了一个非递归版本的DFS。事实证明，一旦节点被压入堆栈或弹出，我就可以将它们标记为“已访问”。我正在解决的问题特别指出，当将其推入堆栈时将其标记为“已访问”。这两个版本都是某种 DFS 吗？或者是一个是DFS，另一个不是。欢迎任何建议。

我认为如果我采用第二种方式，它将模仿递归 dfs。但为什么另一种有效呢？

递归dfs（请忽略这一点）

dfsRec(node)
{
    visitedArray[node]=1;

    for all neighbours of node
        if they aren't visited
            dfsRec(neighbour);
}

dfs(startNode)
{
    visitedArray;
    dfsRec(startNode);  
}

Answer 1

第二种方法（即标记弹出时访问的节点）的问题是，只要图形有循环，您的代码就会永远循环。一旦 DFS 到达该循环，它将继续循环，因为节点在从堆栈中弹出之前不会被标记为已访问，因此通过循环可到达的任何节点都将被一次又一次地推送，直到内存耗尽。

请注意，这个问题与 DFS 的递归实现没有太大区别：递归实现会导致堆栈溢出而不是内存不足，但其原因是相同的。