使用场景

输入数据：如果是递归数据结构，如单链表，二叉树，集合，则一定可以用DFS；如果是非递归数据结构，如一维数组，二维数组，字符串，图，则概率小一点。

状态转换图：树或图

求解目标：必须要走到最深（如树，必须走到叶结点）才能得到一个解，这种情况适合用DFS

思考的步骤

1.是求路径条数，还是路径本身(或动作序列)？

DFS最常见的三个问题，求可行解的总数，求一个可行解，求所有可行解。

（a）如果是路径条数，则不需要存储路径

（b）如果是求路径本身，则要用一个数组path[]存储路径。和BFS不同，BFS虽然最终求的也是一条路径，但需要存储扩展过程的中所有路径，在没有找到答案之前所有路径都不能放弃；而DFS，在搜索过程中始终只有一条路径，因此用一个数组就足够了。

2.只要求一个解，还是要求所有解？

如果只要求一个解，那就找到一个解就可以返回

如果要求所有解，找到一个后，还要继续扩展，知道遍历完

BFS一般只要求一个解，因此不需要考虑这个额问题(BFS当然也可以求所有解，这时需要扩展到所有叶子结点，相当于在内存中存储整个状态转换图，非常占内存，因此BFS不适合解这类问题)

3.如何表示状态？

即一个状态需要存储那些必要的数据，才能完整提供如何扩展到下一步状态的所有信息。和BFS不同，DFS的惯用写法，不是把数据记录在状态struct里，而是添加函数参数（有时为了节省递归堆栈，用全局变量），struct里的字段与函数参数一一对应。

4.如何扩展状态？

这一步和上一步相关。状态里记录得数据不同，扩展方法也就不同。对于固定不变的数据结构（一般题目直接给出，作为输入数据），如二叉树，图等，扩展方法很简单，直接往下一层走，对于隐式图，要先在第一步里想清楚状态所带的数据。

5.关于判重

（a）是否需要判重？如果状态转换图是一棵树，则不需要判重，因为在遍历过程中不可能重复；如果状态转换图是一个DAG，则需要判重。这一点和BFS不同，BFS的状态转换图总是DAG，必须要判重。

（b）怎样判重？和BFS相同！！同时DAG说明存在重叠子问题，此时可以用缓存加速。

6.终止条件是什么？

终止条件是指到了不能扩展的末端节点。对于树，是叶子结点，对于图或者隐式图，是出度为0的节点

7.收敛条件是什么？

收敛条件是指找到了一个合法解的时刻。如果是正向DFS（父状态处理完才进行递归，即父状态不依赖子状态，递归语句一定是在最后，尾递归），则是指是否达到目标状态；如果是逆向DFS（处理父状态时需要先知道子状态的结果，此时递归语句不在最后），则是指是否达到初始状态。

由于很多时候终止条件和收敛条件是合二为一的，因此很多人不区分这两种条件。仔细区分这这两种条件是很有必要的。

为了判断是否到了收敛条件，要在函数接口里面用一个参数记录当前的位置（或距离目标还有多远）。如果是求一个解，直接返回这个解；如果是求所有解，要在这里收集解，即把第一步中表示路径的数组path[]复制到解集合里面。

8.如何加速？

（a）剪枝。 无通用方法，具体分析，在中间节点提前返回。

（b）缓存。

i。提前条件：状态转换图是一个DAG.DAG--》存在重叠子问题--》子问题的解会被重复利用，用缓存能加速。如果依赖关系是树状的（如树，单链表等），没有必要加缓存，因为子问题只会一层层往下，用一次就再也不会用到，加了缓存也没有啥加速效果。

ii。具体实现：可以用数组/HashMap。维度复杂的，用HashMap，C++有map，C++11以后用unordered_map，比map快。

拿到一个题目，回忆上面8个问题，对于树，不需要回答第5和第8个问题。

------------------------------------------------------------------------------------------

dfs模板 
 *input 输入数据指针
 *path  当前路径，也是中间结果
 *result存放最终结果
 *cur/gap标记当前位置/距离目标的距离
 *return 路径长度，如果是求路径本身，则不需要返回长度

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       *dfs模板
     
    
   

    

     

    
    

     

       *input 输入数据指针
     
    
   

    

     

    
    

     

       *path 当前路径，也是中间结果
     
    
   

    

     

    
    

     

       *result存放最终结果
     
    
   

    

     

    
    

     

       *cur/gap标记当前位置/距离目标的距离
     
    
   

    

     

    
    

     

       *return 路径长度，如果是求路径本身，则不需要返回长度
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      void dfs(type &input,type &path,type &result ,int cur or gap){
     
    
   

    

     

    
    

     
    if(数据非法) return 0;//终止条件
     
    
   

    

     

    
    

     
    if(cur==input.size()){//收敛条件
     
    
   

    

     

    
    

     
    //if(gap==0){
     
    
   

    

     

    
    

     

                 将path放入result
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    if(可以剪枝) return;
     
    
   

    

     

    
    

     
    for(...){//执行所有可能的扩展动作
     
    
   

    

     

    
    

     

              执行动作，修改path
     
    
   

    

     

    
    

     
        dfs(input,step+1 or gap--,result);
     
    
   

    

     

    
    

     

              恢复path
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  
 

DFS和回溯法的区别

回溯法=DFS+剪枝

DFS和递归的区别

递归和迭代是对应的。

DFS可以用递归实现，也可用栈实现

递归一般总是用来实现DFS

递归有两种加速策略：（1）剪枝：对中间结果进行判断，提前返回（2）缓存：缓存中间结果，防止重复计算，用空间换时间

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/103866516