深搜理论基础

dfs搜索过程

可一个方向搜，不到黄河不回头。

两个关键点：

• 认准一个方向搜，碰壁后再换方向
• 换方向是撤销原路径，改为节点连接的下一个路径，回溯

代码框架

基础框架

void dfs(参数){
    处理节点
    dfs(图，选择的节点); // 递归
    回溯，撤销处理结果
}

回溯法框架

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

图论中dfs框架

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

深搜三部曲

1. 确认递归函数，参数 可以在写函数实现时，需要什么参数再去补充什么参数 一般，深搜需要 二维数组 保存所有路径，需要 一维数组 保存单一路径。
2. 确认终止条件 其实很多 dfs 写法，没有写终止条件，其实终止条件隐藏在下面 dfs 递归的逻辑里了，也就是不符合条件，直接不会向下递归。
3. 处理目前搜索节点出发的路径 一般是一个 for 循环，遍历当前节点连接的其他所有节点