recursion - 如何在递归调用中维护值？

Question

让我们假设，我们有一个双向图，如下所示

现在，来自源 8 的 DFS 遍历将是 8 1 2 3 6 7 4 5。递归实现

vector <int>  v[10001];
bool visited[10001];
void DFS(int s)
{
 visited[s]=true;
 cout<<s<<" ";
 for(int i=0;i<v[s].size();i++)
 {

 if(!visited[v[s][i]])
 {
     DFS(v[s][i]);
 }
 }
}

所以首先它会递归地去 8->1->2->3 , 8->6 , 8->7->4->5

现在，使用此功能，我还想跟踪每个节点与其源的距离。让我们将其称为 dist[N]，其中 N=节点数。在此图中，dist[8]=0，dist 1 =1，dist[2]=2，依此类推。我该如何实施？

起初我尝试保留一个变量 d 并增加它，如下面的代码所示

int d=0;
void DFS(int s)
{
 visited[s]=true;
 cout<<s<<" ";
 dist[s]=d;
 d++;
 for(int i=0;i<v[s].size();i++)
 {
 if(!visited[v[s][i]])
 {
     DFS(v[s][i]);
 }
 }
}

但很明显，d 的值必须在再次达到 8 时重置为 0，否则根据上述函数 dist[6] 将是 1+ dist[3]。如何克服这一点？另外，有没有更有效的方法来实现这一点？

Answer 1

它可以作为下一次迭代的参数，而不是具有全局变量跟踪深度。

void DFS(int s, int d)
{
 visited[s]=true;
 cout<<s<<" ";
 dist[s]=d;
 for(int i=0;i<v[s].size();i++)
 {
     if(!visited[v[s][i]])
    {
       DFS(v[s][i], d+1);
    }
 }
}