深度优先遍历(DFS)是一种从根节点出发、沿分支尽可能深入探索的算法,核心特点是“一条路走到底再回溯”。其核心亮点包括:递归或栈实现、适合解决路径类问题、空间复杂度较低(O(h),h为树高)。
- 递归实现:通过函数自我调用来遍历,代码简洁。例如二叉树遍历中,先访问根节点,再递归处理左子树和右子树,直到叶子节点后回溯。
- 栈模拟非递归:用栈保存待访问节点,每次取栈顶元素并压入其子节点,确保后进先出的探索顺序,避免递归的堆栈溢出风险。
- 应用场景:适合拓扑排序、连通性检测、迷宫求解等需“深入探索”的问题,如检测图中环的存在或生成全排列。
- 与广度优先(BFS)对比:DFS优先探索深度,可能更快找到目标解;而BFS逐层展开,适合最短路径问题。
提示:实际使用时需注意终止条件(如避免重复访问),并根据问题特性选择递归或栈实现。