本文目录
- 1 深度优先搜索
- 2 示例说明：迷宫路径查找
- 2.1 问题描述
- 2.2 DFS解决逻辑
- 2.3 python代码
- 3 算法应用
- 3.1 数独问题
- 3.1.1 DFS求解逻辑
- 3.1.2 python代码
- 3.2 单词搜索
- 3.2.1 python代码
- 3.2.2 代码逻辑
- 4 总结
- 4.1 优点
- 4.2 缺点
1 深度优先搜索
深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树或图的算法。通过探索尽可能深的分支，DFS 采用递归或迭代的方式实现，直到不能再继续为止，然后回溯到上一个节点继续探索其他分支。
基本原理
DFS 的核心思想是尽可能深地访问每一个节点。当到达一个节点的所有邻接节点都已经被访问过后，算法会回溯到该节点的父节点，继续遍历其他未被访问的节点。这个过程可以通过递归或使用栈来实现。
DFS 的具体步骤
(1)选择起始节点：选择一个未访问的节点作为起始点。
(2)访问节点：将该节点标记为已访问，可以进行某种处理（如打印该节点）。
(3)递归访问相邻节点：对每一个未被访问的邻接节点，递归执行 DFS。
(4)回溯：当所有邻接节点都被访问后，回到上一个节点，探索其他未访问的邻接节点。
(5)重复：直到所有节点都被访问。
实现方式
DFS 可以通过递归或栈实现。
