图的深度优先搜索算法

描述

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。

DFS 的基本思想是从一个初始节点开始，尽可能[深入地探索]其子节点，直到无法继续深入 为止，然后回溯到上一个节点，继续探索其他未访问过的分支。这种策略类似 于[树的先序遍历] 。

DFS 的基本步骤

1. 选择一个其实节点: 选择图中的任意一个节点作为起始节点
2. 标记节点为已访问: 将当前节点标记为已访问，避免重复访问
3. 递归访问相邻节点: 对于当前节点的每一个未访问过的相邻节点，递归地执行 DFS
4. 回溯: 当当前节点的所有相邻节点都被访问过之后，回溯到上一个节点，继续访问 其他未访问过的分支