DFS

1. 访问初始顶点v,并标记为已访问。
2. 从v出发深度遍历，首先遍历v的第一个邻接顶点w。
3. 对w做步骤2的操作,一直遍历到树的最深处。
4. 如果不能继续向下遍历,就返回上一层顶点,并从这个顶点出发寻找下一个未访问的邻接顶点。
5. 重复3、4直到遍历完所有连通分量。

DFS的主要特点:

1. 不需要按序访问顶点,可以在任一顶点作为根开始。
2. 可能存在死胡同,需要回溯。
3. 对不连通的图,无法完全遍历。
4. 时间效率比BFS高,空间复杂度较高。

常见应用:

1. 寻找全部路径 - 比如迷宫求解、骑士巡逻问题
2. 检测环 - 对有向无环图的拓扑排序
3. 二叉树相关问题 - 遍历二叉树
4. 排列组合问题