深度优先遍历（Depth First Traversal）

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

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

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

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

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

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

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

要了解这种算法在C编程语言中的实现， 请单击此处 。