Java实现Dfs算法（基本讲解）-拓冰建站

一、Dfs算法的概念

二、Dfs算法的设计步骤

三、Dfs算法模板

四、Dfs算法经典例题

（1）全排列

（2）N皇后

一、Dfs算法的概念

Depth First Search 即 DFS，意为深度优先搜索，是所有的搜索手段之一。它是从某个状态开始，不断进行状态转移，直到不能转移后，向后回退，一直到遍历完所有的状态。

作为搜索算法的一种，DFS 主要是用于解决 NP 完全问题。但是，深度优先搜索算法的时间复杂度较高，深度优先搜索是 O(n!) 的阶乘级算法，它的效率非常低，在数据规模变大时，此算法就难以解决当前的问题了。

二、Dfs算法的设计步骤

按照定义设计：

确定该题目的状态（包括边界）

找到状态转移方式

找到问题的出口，计数或者某个状态

设计搜索
int check(参数)
{if(满足条件)return 1;return 0;
}
bool pd(参数){相应操作
}
void dfs(int step)
{判断边界pd(){不在边界内，即回溯}尝试每一种可能{满足check条件标记继续下一步dfs(step+1)恢复初始状态（回溯的时候要用到）}
}

三、Dfs算法模板

public static int dfs(int step){if(当前状态=目标状态){return ...;}for(查找新状态){标记状态;dfs(下一状态);撤销状态标记，也就是回溯;}}

四、Dfs算法经典例题

（1）全排列

题目描述

按照字典序输出自然数 11 到 �n 所有不重复的排列，即 �n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 �n。

输出格式

由 1∼�1∼n 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 55 个场宽。

输入输出样例

输入 #1复制
3
输出 #1复制
    1    2    31    3    22    1    32    3    13    1    23    2    1
说明/提示

1≤�≤91≤n≤9。
import java.util.*;public class Main {static int[] v=new int[20];//判断数i是否访问static int n;static int[] a=new int[20];//保存方案public static void main(String[] args) {Scanner scanner=new Scanner(System.in);n=scanner.nextInt();dfs(1);}public static void dfs(int x){//x表示第几个数了if(x>3){for(int i=1;i<=n;i++){System.out.print(a[i]+" ");}System.out.println();}for(int i=1;i<=n;i++){if(v[i]==0){a[x]=i;v[i]=1;dfs(x+1);v[i]=0;}}}
}

（2）N皇后

N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后，
要求：任何两个皇后不同行，不同列也不在同一条斜线上，
求给一个整数 n ，返回 n 皇后的摆法数。

数据范围: 1≤�≤91≤n≤9

要求：空间复杂度 �(1)O(1) ，时间复杂度 �(�!)O(n!)

例如当输入4时，对应的返回值为2，

对应的两种四皇后摆位如下图所示：

示例1

输入：
1
复制返回值：
1
复制

示例2

输入：
8
复制返回值：
92
import java.util.*;public class Main {static int[] zx=new int[200];//左斜static int[] yx=new int[200];//右斜static int[] li=new int[30];//列static int n;static int sum=0;//记录方案数public static void main(String[] args) {Scanner scanner=new Scanner(System.in);n=scanner.nextInt();dfs(1);System.out.println(sum);}public static void dfs(int s){//s表示当前第几行if(s>n){sum++;}//循环找第几列for(int i=1;i<=n;i++){if(check(s,i)){li[i]=1;zx[s+i]=1;yx[s-i+100]=1;dfs(s+1);li[i]=0;zx[s+i]=0;yx[s-i+100]=0;}}}public static boolean check(int x,int y){//判断（x,y)是否满足条件if(li[y]==0&&zx[x+y]==0&&yx[x-y+100]==0){return true;}else{return false;}}}