C++ 深度优先搜索（DFS）算法详解及回溯操作

#include<bits/stdc++.h> using namespace std; const int N=1010; int g[N][N],dist,max_d=-10*N,n,m; bool 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; }

在深度优先搜索中，我们使用一个标记数组来标记哪些节点已经被访问过。在搜索过程中，我们会将当前节点标记为已访问，然后递归访问它的所有未访问邻居节点。当回溯到当前节点时，我们需要将它的标记取消，以便在后续搜索中再次访问它。

在这个代码中，我们使用了一个全局的标记数组 vis。在 dfs 函数中，我们首先将当前节点标记为已访问，然后递归访问它的所有未访问邻居节点。当回溯到当前节点时，我们需要将它的标记取消，以便在后续搜索中再次访问它。因此，在 dfs 函数中，我们需要在回溯时将 vis 数组对应的位置重新赋值为 0。

为什么回溯在 for 循环外面赋值 0 呢？这是因为我们需要在一次完整的搜索结束后，将所有节点的标记都取消，以便进行下一次搜索。因此，在 for 循环外面清空 vis 数组是必要的。如果在 for 循环内清空 vis 数组，那么只有当前节点及其子树中的节点的标记会被取消，而其他节点的标记仍然存在，导致后续搜索出现错误。