深度优先遍历

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

Depth First Travesal

如在上面给出的示例中，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 没有任何未访问的相邻节点，因此我们不断弹出堆栈，直到找到具有未访问的相邻节点的节点。在这种情况下，没有，我们会一直弹出，直到堆栈为空。