algorithm - 对有向图进行 DFS 和 BFS

Question

假设我们有一个图表，例如:

如果你想要一条从 0 到 5 的路径，如果我们在这个图上执行 DFS 和 BFS，我们将以什么顺序访问节点(假设最低的元素总是先被压入)。我无法概念化这些算法如何适用于带循环的图形，我希望有人可以概述每个程序在这样的图形上所采用的过程。

Answer 1

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

从上到下堆叠。

DFS:

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 做。