递归，回溯，DFS，BFS的理解和模板

发表于 | 分类于

LeetCode 里面很大一部分题目都是属于这个范围，例如Path Sum用的就是递归+DFS，Path Sum2用的是递归+DFS+回溯

这里参考了一些网上写得很不错的文章，总结一下理解与模板

递归

递归：就是出现这种情况的代码： （或者说是用到了栈）

解答树角度：在dfs遍历一棵解答树

优点：结构简洁

缺点：效率低，可能栈溢出

递归的一般结构：

1
2
3
4
5
6
7
8
9
10
11
void f()
{
     if(符合边界条件)
    {
       ///////
        return;
    }
    
     //某种形式的调用
     f();
}

回溯

回溯：递归的一种，或者说是通过递归这种代码结构来实现回溯这个目的。回溯法可以被认为是一个有过剪枝的DFS过程。

解答树角度：带回溯的dfs遍历一棵解答树

回溯的一般结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int 当前状态)
	{
	      if(当前状态为边界状态)
	      {
	        记录或输出
	        return;
	      }
	      for(i=0;i<n;i++)		//横向遍历解答树所有子节点
	     {
	           //扩展出一个子状态。
	           修改了全局变量
	           if(子状态满足约束条件)
	            {
	              dfs(子状态)
	           }
	            恢复全局变量//回溯部分
	        }
	}

BFS&DFS

常用的搜索方式。

  1. 枚举。枚举运算量很大，需要预先确定枚举的定义域。
  2. 广度优先搜索（BFS ）——通常可以用于计算图的连通性、单源最短路径、计算最小操作次数等。
  3. 深度优先搜索（DFS）——经典题：火力中心布局。

BFS的占用的是队列的空间

DFS 占用的是栈的空间（因为递归）

BFS和DFS的空间复杂度恰好相反

对链状图，BFS最好（队列中最多只有1个元素），DFS最差（所有节点都在根节点的递归内）

对起点与其他所有点相邻的图，DFS最好（递归深度为1），BFS最差（队列中放满了所有与起点相邻的图）。

BFS模版

1
2
3
4
5
6
7
8
9
10
11
12
13
queue<type> q;
q.push(初始状态);
while (!q.empty())
{
  type t = q.front() ;
  q.pop();
  遍历 t 的各个Next状态  next
  { 
    if (next is legal)
      q.push(next); 计数或维护等; 
  } 
}

但是BFS的状态数一多，需要的空间就会较大。因此就需要状态压缩，BUPT OJ上的1180就是一个典型的例子，但是状态压缩以及解压的时候，又会涉及效率，反正1180将80M的状态压缩到40K以后就超时了……

DFS模板

1
2
3
4
5
6
7
8
9
10
DFS（顶点） 
{
　　处理当前顶点，记录为已访问
　　遍历与当前顶点相邻的所有未访问顶点
　　{
　　　　　　标记更改;
　　　　　　DFS( 下一子状态);
　　　　　　恢复更改;
　　}
}

回溯法：DFS适用于 显式图，但是对于一些隐式关系，我们需要使用回溯法，通过定义或找到各个状态、边界条件、搜索范围、约束条件和最优解结果进行建模求解。

边界条件：达到某状态时，需要检查并确定是继续搜索还是回到上一状态的条件（例如当前已使用时间比当前最优解要长，此时就不需要再进行搜索）

搜索范围：当前从当前状态开始进行搜索的所有下一级状态。

搜索范围：

另外一定要注意，假如参与递归的参数不是通过传参形式的方式进入递归的话，那么一定要做好数据恢复。 

1
2
3
4
5
6
7
8
9
10
11
12
13
Trace（当前状态） 
{
    if 当前状态是结束状态
    {
         if 是最佳解： 记录。
         退出
    }
    遍历当前状态的各个邻接状态
    {
        if 当前状态满足约束条件 且 满足最优性要求 ： Trace（子状态） 
    } 
}