深度优先搜索
深度优先搜索（Depth-First Search, DFS）是一种基于栈结构的搜索策略。
基本思想
从起始状态出发，沿着一条路径一直深入直到无法继续，然后回溯到上一个分叉点，选择另一条路径继续探索。
数据结构
使用栈（Stack）来存储待探索的路径：
- 当前路径无法继续时，从栈中弹出回到上一个状态
- 新的分支节点入栈
特点
- 更快达到边界：适合需要快速找到解的深度较大的问题
- 空间效率较高：只需存储当前路径上的节点
- 不一定找到最优解：找到的第一个解不一定是最短路径
应用场景
- 图的连通性检测
- 拓扑排序
- 回溯法求解问题（如八皇后、数独）
链接到
- 上一个知识点：5.1 搜索基本策略
- 下一个知识点：5.3 广度优先搜索
- 相关知识点：图的深度优先搜索