dfs理解——以出栈方式的字典序为例(对上一个出栈字典序的完善和强化）

笔者认为，dfs的本质在于试验每一方向和还原。

试验每一方向的含义是：将实际题目中的条件几何化为多个方向，给这些方向赋予优先级（一般采用在dfs函数中写入顺序为优先级，这样比较简单方便），按照优先级的顺序来进行试验，每个节点都有基本相同的方向和优先级的，就可以使用dfs的方式解决。

还原：还原要结合试验方向来看。试验方向的终止有几种可能——到达限制边缘，到达转出终点，该节点所有方向已经遍历。当试验方向终止时，我们需要回到上一节点，这一动作我称为回溯。回溯分为两个部分比较容易理解：第一部分是在几何层面上把依托成几何化坐标的条件回到上一坐标，一般我会把这些几何化的条件作为dfs的参数，将条件几何化的目的本身就是为了便于直接回到上一节点。第二部分是还原，也就是一般情况下比较困难的部分，它不像几何参数那么直接，我们需要找到在各种情况下我们所需要的除几何参数以外的变量的上一状况，最容易的方法是在需要还原的变量改变前用另外的变量将原值记录，然后在回溯时重新赋回原值。（此处需要特别注意，并不是所有变量都需要还原，需要结合题意找出和每一操作撤销密切相关同时又多半作为变化基础的变量）

为了代码的简洁，在有时间充裕的情况下，找到题目的特异性规律可以让还原所需要的变量的过程变得简单明了很多。

此处给出普适思路源代码：

#include<iostream>

using namespace std;

 

int n, m;

int a[15], b[15];

int stack[16];

int top = -1;

 

void dfs(int x, int y){

       if(x == n && y == n){//结束出口，此处到终点

              for(int i = 0; i<n; i++)

                     cout<<a[i]<<" ";

              printf("\n");

              return;

       }

 

//y放在x前，作用为能上先上，不能上再右，和条件希望得到字典序有关

 

//入栈和出栈的操作和还原都对top指针有影响，所以x、y操作部分代码各自对top指针有加减 

 

       if(y<n&&y<x){//限制条件，限定关系条件和边缘

              a[y] = stack[top];//既是赋值出栈序列又是保存栈顶内容 （栈顶内容是每次节点变动栈内容唯一变动的，因为按照这道题意一次只变一个，所以保存栈顶就是保存栈的内容）

              --top;

              dfs(x, y+1);

              ++top;

              stack[top]=a[y];//还原栈顶内容

       }

             

       if(x<n){//限制条件，限定关系是x>=y,但是上面的if已经有这个效果故省略，限定边缘

              ++top;

              b[top] = stack[top];//保存栈顶内容 （因为每个节点都会有栈顶，所以要用数组而不能用单一变量来标识） （栈顶内容是每次节点变动栈内容唯一变动的，因为按照这道题意一次只变一个，所以保存栈顶就是保存栈的内容） 

              stack[top]=x+1;

              dfs(x+1, y);

              stack[top] = b[top];//还原栈顶内容

              --top;

       }

             

      

       return;

}

 

int main(){

       cin >> n;

       dfs(0, 0);

       return 0;

}