我最近实现了一个非递归版本的深度优先搜索（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);  }

回答：

第二种方式（即在节点从栈中弹出时标记为已访问）的缺点是，如果你的图中有环，你的代码会永远循环。一旦DFS到达那个环，它会继续绕圈，因为节点在从栈中弹出之前不会被标记为已访问，所以通过环可达的任何节点都会被反复压入栈，直到内存耗尽。

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