数据结构和深度优先遍历

深度优先搜索(DFS)算法以向深运动的方式遍历图形，并使用堆栈记住在任何迭代中发生死角时获取下一个顶点以开始搜索。

如在上面给出的示例中，DFS算法首先从S到A到D到G到E到B，然后到F，最后到C.它使用以下规则。

• 规则1 - 访问相邻的未访问顶点。 将其标记为已访问。显示它。将其推入堆栈。

• 规则2 - 如果未找到相邻顶点，则从堆栈中弹出一个顶点。 (它将弹出堆栈中的所有顶点，这些顶点没有相邻的顶点。)

• 规则3 - 重复规则1和规则2，直到堆栈为空。

步	穿越	描述
1		初始化堆栈。
2		将 **S** 标记为已访问并将其放入堆栈。从 **S** 探索任何未访问的相邻节点。我们有三个节点，我们可以选择其中任何一个。对于此示例，我们将按字母顺序获取节点。
3		**将A** 标记为已访问并将其放入堆栈。从A探索任何未访问的相邻节点 **.S** 和 **D** 都与 **A** 相邻，但我们只关注未访问的节点。
4		访问 **D** 并将其标记为已访问并放入堆栈。在这里，我们有 **B** 和 **C** 节点，它们与 **D** 相邻，两者都是未访问的。但是，我们将再次按字母顺序选择。
5		我们选择 **B** ，将其标记为已访问并放入堆栈。这里 **B** 没有任何未访问的相邻节点。所以，我们从堆栈弹出 **B。**
6		我们检查堆栈顶部是否返回上一个节点并检查它是否有任何未访问的节点。在这里，我们发现 **D** 位于堆栈的顶部。
7		只有未访问的邻接节点是从 **d** 是 **Ç** 现在。所以我们访问 **C** ，将其标记为已访问并将其放入堆栈。

由于 C 没有任何未访问的相邻节点，因此我们不断弹出堆栈，直到找到具有未访问的相邻节点的节点。在这种情况下，没有，我们会一直弹出，直到堆栈为空。