深度优先搜索 (DFS)
深度优先搜索 (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，将其标记为已访问并放入堆栈。 |
广告