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