Dfs 与 Bfs 混淆
Dfs Vs Bfs confusion
来自 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 的情况下推入队列？
你的困惑可能来自于对树考虑太多，但 BFS 和 DFS 在任何图上都可以 运行。例如，考虑一个带有像 A-B-C-A 这样的循环的图。如果从 A 开始广度优先，您将首先将 B 和 C 添加到列表中。然后，您将弹出 B 并且，除非它们被标记为已访问，否则您将添加 C 和 A 到列表中，这显然是错误的。相反，如果您先从 A 深入，然后您将访问 B，然后从那里转到 C，然后再到 A，除非 A 已被标记访问过。
因此，总而言之，无论采用哪种算法，您都需要在第一次看到顶点时将其标记为可见。然而，如果你只考虑 DAG，你会发现事情变得更容易一些，因为你根本没有像上面那样的任何循环。无论如何，关键是你不会陷入循环，为此有多种变体。设置标志是一种方式，检查一组已访问的顶点是另一种方式，在某些情况下，例如树，您不需要做任何事情，只需按顺序迭代边即可。
来自 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 的情况下推入队列？
你的困惑可能来自于对树考虑太多，但 BFS 和 DFS 在任何图上都可以 运行。例如，考虑一个带有像 A-B-C-A 这样的循环的图。如果从 A 开始广度优先，您将首先将 B 和 C 添加到列表中。然后，您将弹出 B 并且，除非它们被标记为已访问，否则您将添加 C 和 A 到列表中，这显然是错误的。相反，如果您先从 A 深入，然后您将访问 B，然后从那里转到 C，然后再到 A，除非 A 已被标记访问过。
因此，总而言之，无论采用哪种算法，您都需要在第一次看到顶点时将其标记为可见。然而，如果你只考虑 DAG，你会发现事情变得更容易一些，因为你根本没有像上面那样的任何循环。无论如何，关键是你不会陷入循环，为此有多种变体。设置标志是一种方式，检查一组已访问的顶点是另一种方式，在某些情况下，例如树，您不需要做任何事情，只需按顺序迭代边即可。