dfs详解
1，基本概念
dfs是深度优先遍历算法，对树状结构进行深度搜索，从开头一直搜索到目标解，如果搜索到最后不是目标解，就会回溯到第一步，相当于在很多岔路口，每一条路都会走到底，如果走的不是正确的路就会换一条路继续走，直到找到正确答案，与bfs不相同的是dfs一直利用递归的方法来达到目的，
2，基本模板
说实话dfs在我感觉来没有什么基本模板，最需要注意的就是怎么找到递归出口和如何去构造递归，递归位置不对，就会功亏一篑，
public static int check(参数)
{
if(满足条件)
return 1;
return 0;
}
//其实完全不用check这里为了方便理解，
public static void dfs(int k)
{
判断边界
{
相应操作
}
尝试每一种可能//for循环，走每一个岔路口
{
满足check条件//满足题目条件
标记
继续下一步dfs(k+1)
恢复初始状态（回溯的时候要用到）
}
}
3，例题
A，全排列
题面：
按照字典序输出自然数 11 到 n 所有不重复的排列，即 n* 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。输入格式：
一个整数 n*。输出格式：
由 1∼1∼n 组成的所有不重复的数字序列，每行一个序列。
每个数字保留 5 个场宽。
代码：
本题直接利用java写出来会有MLE的错误（内存超出限制），所以后续对他进行了一系列的内存优化，代码从刚开始的几行简洁代码变成了有些长，但是优化效果很好，
package improve;
import java.io.*;
public class Dfs_1_2 {
public static StringBuilder stringBuffer = new StringBuilder();
public static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
public static StreamTokenizer in = new StreamTokenizer(ins);
public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));//以上都是优化内存的代码，效率很高
public final static int []a=new int[20];
public final static boolean[] judege=new boolean[20];
public static int n;
public static void print(){
for(int i=1;i<=n;i++)
stringBuffer.append(" ").append(a[i]);
stringBuffer.append("\n");
}
public static void dfs(int k){
if(k==n){
print();
return ;
}//递归出口，如果k==n的话就说明这一次的填数已经完成就可以输出这一次的数
for(int i=1;i<=n;i++){//相当于总共有n条路，要把每条路中的情况都走一个遍
if(judege[i]==false){//判断是否使用过这个数
judege[i]=true;
a[k+1]=i;
dfs(k+1);//填下一个数字，
judege[i]=false;//回溯一下，不然只能填一遍
}
}
}
public static void main(String [] args) throws IOException {
in.nextToken();
n=(int)in.nval;
dfs(0);
out.println(stringBuffer);
out.close();
}
}
B，八皇后
题面：
个如下的 6×66×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。
上面的布局可以用序列 2 4 6 1 3 52 4 6 1 3 5 来描述，第 �i 个数字表示在第 �i 行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 61 2 3 4 5 6
列号 2 4 6 1 3 52 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 33 个解。最后一行是解的总个数。
输入格式：
一行一个正整数 n，表示棋盘是 n×n* 大小的。
输出格式：
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
代码：
经典dfs题目，还是有优化代码，发现dfs不优化每次都会内存超出限制，
package improve;
import java.io.*;
public class Dfs_2 {
public static StringBuilder stringBuffer = new StringBuilder();
public static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
public static StreamTokenizer in = new StreamTokenizer(ins);
public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
public static int []a =new int[100];
public static boolean []b=new boolean[100];//纵列
public static boolean []c=new boolean[100];//左下到右上的对角线
public static boolean []d=new boolean[100];//右下到左上的对角线
public static int n ;
public static int kk=0;
public static void out()
{
if(kk<=2){
for(int i=1;i<=n;i++)
stringBuffer.append(a[i]).append(" ");
stringBuffer.append("\n");
}
kk++;//记录有几次满足条件的答案
}
public static void dfs(int k){
if(k>n){
out();
return ;
}//递归出口，如果k初值为零就是k==n
for(int i=1;i<=n;i++){
if(b[i]==false&&c[k+i]==false&&d[i-k+n]==false){//判断纵列和对角线上是不是已经被填充
a[k]=i;//填数，
b[i]=true;
c[k+i]=true;
d[i-k+n]=true;
dfs(k+1);//填充下一个数
b[i]=false;
c[k+i]=false;
d[i-k+n]=false;//回溯一下
}
}
}
public static void main(String [] args) throws IOException{
in.nextToken();
n=(int)in.nval;
dfs(1);
out.print(stringBuffer);
out.println(kk);
out.close();
}
}