DFS

DFS基础

栈搜索

运行时栈：栈里的是仍在运行的

入栈：函数开始运行

出栈：函数运行结束

DFS步骤

1. 出栈（即函数被调用了）

2. 捕捉：全局变量捕捉target值

   出队的时候进行目标点的捕捉，如果是目标点就返回，不再继续扩展

3. 扩展

4. 入栈

先序遍历

从已知点开始出发

（写法在本质上与BFS非常相似，本质上还是拓扑排序）

后序遍历

从未知点开始出发

如果需要求拓扑排序的话，只需要在dp[i] = dfs(i - 1) + dfs(i - 2)后面一行加上topo.add(i)即可，因为这里是后续，dp[i]依赖的边已经访问完了

中序遍历：

仅存在于二叉树中，且仅在二叉搜索树上有意义，其他情况下没有实际意义

DFS相对于BFS的优势

• 后序传值（DFS没有后序）
• 先序回溯（BFS不能回溯）
• 宽树搜索