1.dfs的本质就是递归,不同的是在递归的过程中加点料,由于递归的特殊操作模式,人脑很难模拟整个过程,猪脑过载。
2.从排列数字和八皇后可以看出,基本套路是先枚举本层的所有可能,再进行递归,也就是枚举所有本层兄弟的可能,再向下走,而下一层也是这样的过程。
如排列数字:
for(int i=1;i<=n;i++){//这里的循环并不是n层,而是一层的几种可能,或者说是树中兄弟节点。
if(!b[i]){
weizhi[level]=i;
b[i]=true;
dfs(level+1);
b[i]=false;
}
}
八皇后:
dfs(x+1,y,s);//第一种情况,直接不放,不考虑能不能放。
if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[n+y-x]){//第二种情况,考虑能放的问题。
g[x][y]=’Q’;
row[x]=col[y]=dg[x+y]=udg[n+y-x]=true;
dfs(x+1,y,s+1);
row[x]=col[y]=dg[x+y]=udg[n+y-x]=false;
g[x][y]=’.’;
}
3.关于是否回溯,其实只要是递归就要回溯,所以必定有返回值,有的同学认为恢复现场就是回溯,其实是不正确的。
3.关于是否需要恢复现场,如果后面操作涉及到前面的内容,则需要恢复现场,但是如果是树的重心这道题,则不需要,根本原因在于变量的作用范围,用变量记录了子树中节点的个数,每个节点遍历过程也不需要重复,所以不需要恢复现场。
int dfs(int u)
{
st[u] = true;
int size = 0, sum = 0;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (st[j]) continue;
int s = dfs(j);
size = max(size, s);
sum += s;
}
size = max(size, n - sum - 1);
ans = min(ans, size);
return sum + 1;
}
补充一点:递归的逻辑自洽,是能够在某个节点结束递归(一般是在最后一层或者叶子结点),而且不管哪一层的操作过程都是相同的,就可以使用递归,这样理解树的重心会更加容易些!
回溯的本质应该是回到还未选择该状态的上一个状态,而并不是回复现场
回溯是递归的副产品,只要有递归就会有回溯。
确实