algorithm - 在有向图上执行 DFS 和 BFS

Question

假设我们有一个图，例如：

如果你想要一个从 0 到 5 的路径，如果我们在这个图上执行 DFS 和 BFS，我们将按什么顺序访问节点（假设总是首先推送最低元素）。我在概念化算法如何适用于具有循环的图时遇到了麻烦，我希望有人可以概述每个在这种图上所采用的过程。

Answer 1

用于处理循环的常用技术是拥有一组已经访问过的顶点。在将顶点推送到队列/堆栈之前，请检查它是否被访问过。如果它不做任何动作，否则从将其添加到访问集开始，然后继续遍历图。

从上到下堆叠。

文件系统：

empty stack
visiting 0: stack: 2, 1, visited: 0
visiting 2: stack: 5, 3, 1 visited: 0, 2
visiting 5: stack: 4, 3, 1 visited: 0, 2, 5
visiting 4: stack: 3, 2, 3, 1 visited: 0, 2, 4, 5
visiting 3: stack: 4, 2, 3, 1 visited: 0, 2, 3, 4, 5
visiting 4: (nothing to do) - stack: 2, 3, 1 visited: 0, 2, 3, 4, 5
visiting 2: (nothing to do) - stack: 3, 1 visited: 0, 2, 3, 4, 5
visiting 3: (nothing to do) - stack: 3, 1 visited: 0, 2, 3, 4, 5
visiting 1: stack: 3, 0 visited: 0, 1, 2, 3, 4, 5
visiting 3: (nothing to do) - stack: 1 visited: 0, 1, 2, 3, 4, 5
visiting 1: (nothing to do) - stack empty visited: 0, 1, 2, 3, 4, 5
DONE

以类似的方式为 BFS 做。