深度优先搜索(DFS)算法以深度向运动遍历图形并使用堆栈记住在任何迭代中发生死角时获取下一个顶点以开始搜索.
如上面给出的示例所示，DFS算法从S到A到D到达首先是G到E到B，然后到F，最后到C.它使用以下规则.
规则1 : 访问相邻的未访问顶点.将其标记为已访问.显示它.将其推入堆栈.
规则2 : 如果未找到相邻顶点，则从堆栈中弹出一个顶点. (它将弹出堆栈中没有相邻顶点的所有顶点.)
规则3 : 重复规则1和规则2，直到堆栈为空.
| Step | Traversal | 描述 |
|---|---|---|
| 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 ，将其标记为已访问并将其放入堆栈. |
由于 C 没有任何未访问的相邻节点，因此我们不断弹出堆栈，直到找到具有未访问的相邻节点的节点.在这种情况下，没有，我们一直弹出直到堆栈为空.
要了解这种算法在C编程语言中的实现.
