algorithm - Dfs 与 Bfs 混淆

Question

来自topcoder article :

"In BFS We mark a vertex visited as we push it into the queue, not as we pop it in case of DFS."

注意:这是在使用显式堆栈的 dfs 实现的情况下说的。(伪 dfs)。

我的问题是为什么会这样？为什么我们不能标记从队列中弹出后访问的顶点，而是在 bfs 的情况下插入队列？

Answer 1

您的困惑可能来自对树的过多思考，但 BFS 和 DFS 可以在任何图上运行。例如，考虑一个带有循环的图，如 A-B-C-A。如果您从 A 开始进行广度优先，您将首先将 B 和 C 添加到列表中。然后，您将弹出 B 并且，除非它们被标记为已访问，否则您将添加 C 和 A 到列表中，这显然是错误的.相反，如果您先从 A 深入，然后您将访问 B，然后从那里转到 C，然后到 A，除非 A 已被标记为已访问。

因此，总而言之，无论采用哪种算法，您都需要在第一次看到顶点时将其标记为可见。然而，如果你只考虑 DAG，你会发现事情变得更容易一些，因为你根本没有像上面那样的任何循环。无论如何，关键是你不会陷入循环，为此有多种变体。设置标志是一种方式，检查一组已访问的顶点是另一种方式，在某些情况下，例如树，您不需要做任何事情，只需按顺序迭代边即可。