C++ 深度优先搜索 (DFS) 回溯技巧解析：为什么回溯 vis 数组应该在 for 循环后面？

C++ 深度优先搜索 (DFS) 回溯技巧解析：为什么回溯 'vis' 数组应该在 'for' 循环后面？

在 C++ 深度优先搜索 (DFS) 中，我们通常使用一个 'vis' 数组来标记节点是否已被访问。在递归函数返回时，我们需要将 'vis' 数组重置回未访问状态，也就是回溯。

本文将讨论为什么在 'dfs' 函数中，回溯 'vis' 数组的操作通常应该放在 'for' 循环后面，而不是在 'for' 循环内。

代码示例:

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N],dist,max_d=-10*N,n,m;
boolean vis[N];
void dfs(int st){//深度优先搜索 
	for(int i=1;i<=n;i++){
		if(g[st][i]&&!vis[i]){
			vis[i]=1;
			dist+=g[st][i];
			dfs(i);
			dist-=g[st][i];//回溯 
		}
	}
	max_d=max(max_d,dist);//统计最大深度 
	vis[st]=0;
	return;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;//读入边和对应的权值 
		g[x][y]=z;
		g[y][x]=z;
	}
	for(int i=1;i<=n;i++){
        vis[i]=1;
        dfs(i);
        memset(vis,0,sizeof(vis));//记得清空标记数组
    }
    cout<<max_d;
	return 0;
}

问题: 为什么 'dfs' 里面回溯 'vis' 数组在 'for' 循环后面赋值 0，而不是 'for' 循环里面？

分析:

在这个题目中，回溯 'vis' 数组的位置不影响最终结果。因为在 'dfs' 函数中，我们采用了标记法来避免重复访问同一个节点，当我们从一个节点返回时，该节点的标记已经失效。所以在回溯时，将 'vis' 数组的值赋为 0 或者回到调用 'dfs' 函数的上一层时，'vis' 数组已经被重置为调用该层 'dfs' 函数前的状态，对于下一次 'dfs' 调用来说，影响不大。

但是，在其他情况下，回溯数组的位置可能会影响结果。 如果在 'for' 循环内回溯 'vis' 数组，那么当我们回溯到上一层 'dfs' 函数时，该层的 'vis' 数组已经被修改，可能会影响下一次 'dfs' 调用的结果。因此，在一般情况下，我们应该在 'for' 循环外面回溯 'vis' 数组。

总结:

将 'vis' 数组的回溯操作放在 'for' 循环后面，通常可以确保 'vis' 数组在每次 'dfs' 调用前都处于一致的初始状态，从而避免错误的结果。

建议:

在编写 'dfs' 函数时，养成习惯将 'vis' 数组的回溯操作放在 'for' 循环后面，这样可以避免一些潜在的错误。