扩展（剪枝，记忆性搜索，dfs+dp 树形dp较多，dfs+并查集，dfs+贪心，匈牙利算法中的dfs）

一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。
整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

1. 定义的DFS：对图的连通性进行测试，典型的问题：迷宫连通性测试、图的条件搜索等
2. 广义的DFS–DFS思路的应用：DFS搜索顺序+规则问题、穷举结果寻求最优解/符合条件解等等，由于其穷举答案的本质，又被称为爆搜
   
   

int check(参数)
{
    if(满足条件)
        return 1;
    return 0;
}
 
void dfs(int step)
{
        判断边界
        {
            相应操作
        }
        尝试每一种可能
        {
               满足check条件
               标记
               继续下一步dfs(step+1)
               恢复初始状态（回溯的时候要用到）
        }
}   

不会再撤销,从而使得可搜索路径越来越少,而回溯会在访问初标记,回溯时撤销。

个人理解：需不需要在递归返回之后  保留进入函数时的当前状态  。需要保留原始状态回溯  不需要保留原始状态（舍弃）不回溯

sign[i]=1; dfs(i+1);sign[i]=0;     
刚进入函数的时候i标记是0，然后标记上搜下一个，递归返回的时候看我们需不需要保留刚进入函数时候的i标记。
回溯往往紧跟着dfs递归语句后面

常用参数：当前状态标记，步数，累加值
需要找到的：入口，出口，判断条件
只要保证以上三个条件正确，dfs写的就没问题。很多时候去跟踪函数的递归反而会越来越搞不懂。
要相信函数做的事情是对的。

另外dfs有时候会涉及到不同的入口（即入口不确定）这时候要从循环中枚举不同的入口进行求解
例如这道题：https://www.luogu.com.cn/problem/P1434

借鉴提取自：https://blog.csdn.net/yanweiqi1754989931/article/details/109603384?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164774726516780366597483%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=164774726516780366597483&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-8-109603384.142^v2^pc_search_result_control_group,143^v4^register&utm_term=dfs&spm=1018.2226.3001.4187