所以我最近实现了一个非递归版本的 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的递归实现没有太大区别:递归实现会导致堆栈溢出而不是内存不足,但原因是一样的。
关于algorithm - 非递归 dfs(何时标记它已访问?),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19757342/