在有向图上执行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 进行操作。