algorithm - 非递归 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的递归实现并没有太大区别：递归实现会导致堆栈溢出而不是内存不足，但原因是一样的。