1.使用场景

输入数据：如果是递归数据结构，如单链表，二叉树，集合，则一定可以用DFS；
如果是非递归数据结构，如一维数组，二维数组，字符串，图，则概率小一点。
状态转换图：树或图
求解目标：必须要走到最深（如树，必须走到叶结点）才能得到一个解，这种情况适合用DFS

2.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 路径长度，如果是求路径本身，则不需要返回长度 */
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
   }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

3.其他

DFS和回溯法的区别：回溯法=DFS+剪枝
DFS和递归的区别：DFS可以用递归实现，也可用栈实现；递归一般总是用来实现DFS。
递归有两种加速策略：
（1）剪枝：对中间结果进行判断，提前返回
（2）缓存：缓存中间结果，防止重复计算，用空间换时间

4.简单栗子1

有n件物品，每件重量为w[i]，价值为c[i]，现在需要选择出若干物品放入一个容量为V的背包中，使得在选入背包的物品重量和不超过容量V的前提下，让背包中物品的价值之和最大，求最大价值。
（1）未剪枝（暴力）

#include<cstdio>
const int maxn=30;
int n,V,maxValue=0;//物品件数n，背包容量V，最大价值maxValue
int w[maxn],c[maxn];//w[i]为每件物品的重量，c[i]为每件物品的价值
//DFS,index为当前处理的物品编号
//sumW和sumC分别为当前总重量和当前总价值
void DFS(int index,int sumW,int sumC){
	if(index==n){//已经完成对n件物品的选择（死胡同）
		if(sumW<=V&&sumC>maxValue){
			maxValue=sumC;//不超过背包容量时更新最大价值maxValue
		}
		return;
	}
	//岔道口
	DFS(index+1,sumW,sumC);//不选第index件物品
	DFS(index+1,sumW+w[index],sumC+c[index]);//选第index件物品
}
int main(){
	scanf("%d%d",&n,&V);
	for(int i=0;i<n;i++){
		scanf("%d",&w[i]);//读入每件物品的重量
	}
	for(int i=0;i<n;i++){
		scanf("%d",&c[i]);//每件物品的价值
	}
	DFS(0,0,0);//初始时为第0件物品、当前总重量和总价值均为0
	printf("%d\n",maxValue);
	return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
 

输入：

5 8//5件物品，背包容量为8
3 5 1 2 2//重量
4 5 2 1 3//价值

  

 

  
1
  
2
  
3
 

输出：

10

  

 

  
1
 

（2）剪枝版

void DFS(int index,int sumW,int sumC){
	if(index==n){
		return;//已经完成对n件物品的选择
	}
	DFS(index+1,sumW,sumC);//不选第index件物品
	//只有加入第index件物品后未超过容量V，才能继续
	if(sumW+w[index]<=V){
		if(sumC+c[index]>ans){
			ans=sumC+c[index];//更新最大价值maxValue
		}
		DFS(index+1,sumW+w[index],sumC+c[index]);//选第index件物品
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

5.简单栗子2

给定N个整数（可能为负数），从中选择K个数，使得该K个数字之和恰好等于X，如果有多个方案则选择元素平方和最大的一个。

//序列A中n个数选k个数使得和为x，最大平方和为maxSumSqu
int n,k,x,maxSumSqu=-1,A[maxn];f
//temp存放临时方案，ans存放平方和最大的方案
vector<int>temp,ans;
//当前处理index号整数，当前已选整数个数为nowK
//当前已选整数之和为速，当前已选整数平方和为sumSqu
void DFS(int index,int nowK,int sum,int sumSqu){
	if(nowK==k&&sum==x){//找到k个数的和为x
		if(sumSqu>maxSumSqu){//如果比当前找到的更优
			maxSumSqu=sumSqu;//更新最大平方和
			ans=temp;//更新最优方案
		}
		return;
	}
	//已经处理完n个数，或者超过k个数，或者和超过x，返回
	if(index==n||nowK>k||sum>x) return;
	//选index号数
	temp.push_back(A[index]);
	DFS(index+1,nowK+1,sum+A[index],sumSqu+A[index]*A[index]);
	temp.pop_back();
	//不选index号数
	DFS(index+1,nowK,sum,sumSqu);
}	

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
 

如果每个数字都可以选择多次，即当选择了index号数，不应当直接进入index+1号数的处理，即还能够继续选择index号数，直到某个时刻决定不再选择index号数，就会通过“不选index号数”这条分支进入index+1号数的处理——则选index号数的代码改为DFS(index,nowK+1,sum+A[index],sumSqu+A[index]*A[index])。

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

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