DFS中怎么记录当前“递归结点”的状态量

在写PAT A1111这一题的过程中暴露了自己对DFS的认识还不是很深刻，现在将其中遇到的这个问题记录下来（debug了好久好久呜呜呜~），并对这一类问题做个总结。

首先PAT A111是个很常规的dijkstra+DFS这一类题，在寻找时间最短且结点数最少的路径时，所写的代码如下：

int minNum=inf,num=0;
void DFS_time(int u)
{
    num++;
    if(u==st)
    {
        tempPath.push_back(u);
        if(num<minNum)
        {
            minNum=num;
            path_time=tempPath;
        }
        tempPath.pop_back();
        //这里掉了一句
        //num--;
        return;
    }

    tempPath.push_back(u);
    for(int i=0;i<pre_time[u].size();i++)
    {
        DFS_time(pre_time[u][i]);
    }
    tempPath.pop_back();
    num--;
}

这里用num变量记录当前递归状态下的结点总数，但是问题就在于if(u==st)这个分支的结尾并没有写上num--来还原结点个数，导致遍历过一个叶子结点后，num的数值不再准确，于是后面的程序也不再正确。其实这反映的是一类的问题，就是在递归中如何正确处理记录当前”递归结点“的状态量。

当用全局变量记录结点状态时（例如上面的num，tempPath），每到一个新的结点后，状态需要更新，当任意一个结点结束后状态要还原到进入该节点前的状态，上面例子就错在结束叶子结点的访问后并没有将状态复原。

在排查自己错误的时候也在网上看了一些其他人的代码，发现了另一种记录状态量的方法，觉得可以和用全局变量记录的方式做一个比较，相应的代码如下（原帖地址https://blog.csdn.net/zhang35/article/details/107729376）：

void dfs(vector<vector<int> > &pre, vector<vector<int> > &w, int root, int sum, int &minSum, vector<int> path, vector<int> &minPath){
    path.push_back(root);
    if (pre[root].size()==0) {  //到达叶子
        if (sum < minSum){
            minSum = sum;
            minPath = path;
        }
        return;
    }
    for (int i=0; i<pre[root].size(); i++){
        dfs(pre, w, pre[root][i], sum + w[pre[root][i]][root], minSum, path, minPath);
    }
}

//Dijkstra找最短时间路径
vector<int> distT(n, MAXINT);
vector<vector<int> > preT(n);
Dijkstra(src, time, distT, preT);
//dfs找最短路径中节点数最小的
int minT = MAXINT;
vector<int> minPathT;
path.clear();
vector<vector<int> > nodes(n, vector<int>(n, 1));  //经过节点数量，统一为1
dfs(preT, nodes, dst, 0, minT, path, minPathT);

上面是是直接将状态量作为DFS的一个形参传入，即是dfs函数中的sum和path，从代码上看好像并不需要每次去还原状态量的值，这就显示出这种写法的妙处，全局变量记录状态量时每次都需要去改变它的值，然而dfs搜索的过程中状态时刻都在变换，所以必须一直对它进行修改维护；而以形参的形式记录就好像在每个状态结点上都专门加了一个变量，只需要每次给新的状态变量赋值了，不需要总是去修改一个变量了。

当然仔细看的话sum和path的更新方式还是有差别的，sum每次到新的状态是就已经更新完成了，path还需要在开头再push_back，但由于每个状态的形参是相互独立的，它们的改变并不会影响到同一层的结点的状态值。

总结起来说，这种形参的形式可以直接继承或是改变上一层结点的状态量，而同层的结点状态量值只与上一层的状态有关，相互之间不影响，所以不用去还原状态变量值