Data Structures Algorithms 简明教程
Depth First Search (DFS) Algorithm
Depth First Search (DFS) Algorithm
深度优先搜索（DFS）算法是一种递归算法，用于搜索图或树数据结构的所有顶点。此算法以深入运动遍历图，并使用堆栈记住要获取下一个顶点以开始搜索，当在任何迭代中发生死锁时。
正如上面给出的示例中，DFS 算法首先从 S 到 A 到 D 到 G 到 E 到 B，然后到 F，最后到 C。它采用以下规则。
-
Rule 1 - 访问邻接的未访问顶点。将其标记为已访问。显示它。将其推入堆栈。
-
Rule 2 - 如果未找到邻接顶点，则从堆栈弹出一个顶点。（它将弹出堆栈中所有没有邻接顶点的顶点。）
-
Rule 3 - 重复规则 1 和规则 2，直到堆栈为空。
由于 C 没有任何未访问的邻接节点，因此我们将继续弹出堆栈，直到找到具有未访问邻接节点的节点。在这种情况下，没有，并且我们一直弹出，直到堆栈为空。