我试图理解维基百科 (http://en.wikipedia.org/wiki/Depth-first_search) 上的规范 DFS 伪代码——特别是使用堆栈的非递归实现。
在 BFS 中，您在将节点插入队列之前检查它是否已被探索，这保证了不会将任何节点插入队列超过一次。但是在 DFS 中，当你将一个节点从堆栈中弹出时，你只检查它是否已经被探索过。这似乎是故意的，正如维基百科页面所说:“[DFS] 延迟检查是否已发现顶点，直到从堆栈中弹出顶点，而不是在推送顶点之前进行此检查。”
但似乎这种延迟可能会导致节点不止一次被压入堆栈。例如，考虑一下图，其中节点 1 指向节点 2，节点 2 指向节点 3，节点 4 指向节点 4，依此类推，直到节点 100。这些节点中的每一个都指向节点 0。
考虑将维基百科 DFS 算法应用于此图，并将节点 1 作为起始状态。首先，节点 0 将被压入堆栈。然后将推送节点 2。接下来，节点 2 将从堆栈中弹出，并且由于尚未探索，其子节点将被压入堆栈(无需检查它们是否已添加到堆栈!)。节点 2 的子节点是节点 0 和节点 3。接下来，节点 3 将展开，将节点 0 和节点 4 压入堆栈。这将一直持续到堆栈中出现 100 次节点 0 为止。
我的问题是:为什么 DFS 与 BFS 不同，因为它会延迟探索检查(如果它会产生这种冗余)？
最佳答案
我认为您从字面上理解了维基百科算法，而不是考虑访问/发现节点意味着什么。同样在 BFS 中，您可以将一个节点的所有子节点/相邻节点插入队列，但是您必须丢弃已经发现的节点； DFS 也是如此。
在 BFS 和 DFS 中，您可以选择:
- 不推送已经发现的节点。 或者
- 推送所有相邻节点，但在弹出时丢弃那些已经发现的节点。
BFS 和 DFS 之间的唯一区别是，您在 BFS 中插入堆栈，而在 DFS 中插入队列。
关于algorithm - 深度优先搜索会产生冗余吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25988965/