数据结构DFS深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着每个分支尽可能深入地探索，直到到达叶子节点，接着回溯到上一个节点，继续探索其他未访问的分支。DFS常用于解决路径查找、连通性分析、拓扑排序等难题。
一、DFS的基本想法
DFS的核心想法是“先访问当前节点，再递归地访问其所有相邻未被访问过的节点”。该经过通过栈（或递归调用栈）来实现，确保在访问完一个分支后能够回到之前的节点继续处理其他分支。
二、DFS的实现方式
DFS可以通过递归或非递归（显式栈）的方式实现。递归技巧更为简洁，但可能会因递归深度过大而出现栈溢出难题；非递归技巧则更可控，适合处理大规模数据。
| 实现方式 | 优点 | 缺点 |
| 递归 | 代码简洁，逻辑清晰 | 可能导致栈溢出，效率较低 |
| 非递归 | 控制灵活，避免栈溢出 | 代码复杂，需要手动维护栈 |
三、DFS的应用场景
DFS适用于下面内容几种情况：
1. 寻找路径：如迷宫求解、图中两点之间的路径。
2. 判断连通性：判断图中两个节点是否连通。
3. 生成所有可能的解：如八皇后难题、排列组合等。
4. 拓扑排序：对有向无环图进行排序。
5. 检测环路：判断图中是否存在环。
四、DFS与BFS的区别
| 特征 | DFS | BFS |
| 遍历顺序 | 深入优先 | 广度优先 |
| 存储结构 | 栈（递归） | 队列 |
| 空间复杂度 | O(h)（h为树高） | O(n) |
| 适用场景 | 寻找路径、连通性 | 最短路径、层次遍历 |
| 是否容易找到最短路径 | 否（不一定） | 是 |
五、DFS的优缺点拓展资料
| 优点 | 缺点 |
| 实现简单，易于领会 | 不一定能找到最短路径 |
| 能有效处理树和图结构 | 内存消耗较大（递归） |
| 适合深度较大的结构 | 无法处理无限大的图 |
六、拓展资料
DFS是一种基础且重要的图遍历算法，广泛应用于各种实际难题中。虽然它在某些情况下不如广度优先搜索（BFS）高效，但在处理深度优先的难题时具有明显优势。掌握DFS的原理和实现方式，对于领会和应用数据结构与算法具有重要意义。
