深度优先遍历（DFS）是一种遍历树或图的方法，它沿当前路径深度优先搜索，直到无法再深入为止，再回溯到上一个未访问过的节点。与广度优先遍历（BFS）不同，DFS 不会一次访问所有同级节点，而是深入探索一条路径。

DFS 的递归实现

DFS 可以使用递归轻松实现，递归是一种函数调用自身的方法。在 DFS 实现中，该函数将访问当前节点，然后递归调用自身来遍历当前节点的所有子节点。一旦所有子节点都被遍历，该函数将回溯到调用它的函数，并继续遍历剩余的节点。

DFS 的步骤

1. 初始化：从树的根节点开始，创建一个空栈。

2. 访问：将根节点压入栈中，并标记其为已访问。

3. 重复：

- 如果栈不为空，则：

- 弹出栈顶元素，并访问它。

- 如果它有任何未访问的子节点，则将子节点压入栈中。

- 否则，DFS 结束。

DFS 的优点

- 简单明了：DFS 的递归实现简洁而易于理解。

- 内存占用少：DFS 只需要一个栈来存储已访问的节点，因此内存占用较少。

- 适用于深度搜索：DFS 适用于需要深度搜索的场景，例如查找特定节点或检查树的高度。

DFS 的缺点

- 可能出现栈溢出：如果树非常深，DFS 可能会导致栈溢出，因为栈存储了访问过的所有节点。

- 效率较低：对于宽树，DFS 可能效率较低，因为它需要反复回溯和重新遍历节点。

- 无法一次访问同级节点：DFS 无法一次访问所有同级节点，这使得某些操作（例如计算树的宽度）变得困难。

DFS 的应用

- 查找特定节点：DFS 可以高效地查找树或图中的特定节点。

- 检查树的高度：DFS 可以通过跟踪访问过的最深路径来检查树的高度。

- 查找环：DFS 可以用于检测图中的环，因为如果访问过的节点被重新访问，则存在环。

- 拓扑排序：DFS 可以用于对有向无环图（DAG）进行拓扑排序，即找到一个排列，使得每个节点都位于其所有后继节点之前。

- 连通性：DFS 可以用于确定树或图中的连通分量，即所有可以互相到达的节点的集合。

DFS 的变体

- 前序遍历：在访问节点之前对其进行处理。

- 中序遍历：在访问节点的子节点之前对其进行处理。

- 后序遍历：在访问节点的所有子节点之后对其进行处理。

- 迭代 DFS：使用栈或队列实现 DFS 的非递归版本。

- 深度优先搜索（IDDFS）：一种修改后的 DFS，它使用深度限制来防止栈溢出。

DFS 的时间复杂度

DFS 的时间复杂度取决于树或图的大小和结构。对于一棵具有 V 个节点和 E 条边的二叉树，DFS 的时间复杂度为 O(V+E)。对于更复杂的树或图，时间复杂度可能更高。

DFS 的空间复杂度

DFS 的空间复杂度取决于使用的递归调用深度。对于一棵具有 V 个节点的二叉树，DFS 的空间复杂度为 O(V)，因为每个递归调用都需要存储一个栈帧。对于更复杂的树或图，空间复杂度可能更高。

DFS 的示例

考虑以下二叉树：

```

1

/ \

2 3

/ / \

4 5 6

```

使用 DFS 的中序遍历将输出：

```

4 2 5 1 6 3

```

DFS 的练习题

1. 如何使用 DFS 实现树的高度计算？

2. 如何使用 DFS 查找有向无环图中的环？

3. 如何使用 DFS 拓扑排序有向无环图？

4. 如何修改 DFS 以进行深度优先搜索（IDDFS）？

5. 给定一棵二叉树，如何使用 DFS 查找具有最大值的节点？

DFS 的其他资源

- [深度优先搜索（DFS）算法及其应用](

- [深度优先搜索（DFS）的 Python 实现](

- [深度优先搜索（DFS）的 C++ 实现](