深搜优化

深搜优化【updating…】

1.深搜是什么？

2.深搜优化？

深搜是很消耗资源和时间的一种方法，这里给出深搜方法的两种不同写法，并比较其中的效率：

• DFS1

void DFS1(int s){
	if(child[s].size()==0) return;//如果没有相邻节点了，则直接返回 
	vis[s]=true;//标记为已经访问了 
	for(int i=0;i<child[s].size();i++)
		if(!vis[child[s][i]]) DFS(child[s][i]); 
}

• DFS2

void DFS2(int s){
	if(vis[child[s][i]]) return;
	if(child[s].size()==0) return;//如果没有相邻节点了，则直接返回 
	vis[s]=true;//标记为已经访问了 
	for(int i=0;i<child[s].size();i++)
		DFS(child[s][i]); 
}

可以看到DFS1是先判断，再进入函数；但是 DFS2是先进入函数，再判断。给人的直观感受是：DFS1函数会更加高效。